https://www.luogu.org/problemnew/solution/P3467 BZOJ1113[POI2008] 海报PLA
具体栗子在课件里 N个矩形楼房,排成一排. 现在希望用尽量少的矩形海报Cover住它们. 必有至少一栋楼房被完全覆盖 f[i]表示将第i幢房屋完全覆盖，并以该房屋的高度将广告向左延伸的最大距离 对称地求向右延伸的情况，就可以求出最大答案 f[i]=？ 从左向右枚举第i幢房子，将其完全覆盖 即使第i-1幢房子的高度高于第i栋房子，无论高出多少，多余的高度在枚举到i之后都是无用的 为啥可以这么删去 如果ai-1 > ai，那么i右边的房子向左延伸时，如果没有被i挡住，则更不会被i-1挡住 删除操作可能连续发生 由i删除i左边的房屋 每删除一幢房屋就说明又能向左 扩展一段距离
#include<cstdio> #include<iostream> using namespace std; int t,di,wi; const int maxn=2500000; int stack[maxn],ans,num; int top; int main() { scanf("%d",&t); for(int i=1;i<=t;i++) { cin>>di>>wi; while(top>0&&stack[top]>=wi) { if(wi==stack[top]) num++; --top;//弹栈操作 } stack[++top]=wi; } printf("%lld\n",t-num); return 0; }转载于:https://www.cnblogs.com/tbdemons/p/11296864.html
相关资源：JAVA上百实例源码以及开源项目