前置知识
解法
容易有每个建筑物的宽度对答案没有影响,故可以将其宽度均看作 \(1\)。
在最优策略下,对于每张海报,其高度一定等于所覆盖的楼的最小高度。
单调栈维护最小高度,记录额外海报数量(与先前高度相等时可以少用一张海报)。
最终,用总张数 \(n\) 减去额外海报数量即可。
代码
#include<bits/stdc++.h>
using namespace std;
stack<int>s;
int main()
{
int n,i,x,y,ans=0;
cin>>n;
s.push(0);
for(i=1;i<=n;i++)
{
cin>>x>>y;
while(s.empty()==0&&y<=s.top())
{
if(s.top()==y)
{
ans++;
}
s.pop();
}
s.push(y);
}
cout<<n-ans;
return 0;
}
后记
多倍经验:luogu P3467 [POI2008] PLA-Postering
标签:海报,Postering,题解,POSTERIN,高度,int,SP15620 From: https://www.cnblogs.com/The-Shadow-Dragon/p/18284694