ccf试题 最大的矩形

第一反应是要动态规划，感觉里面挺复杂的。本来动态规划一般我都不会做，就直接搜题解了，没想到可以这么简单。。。看来最大的敌人是自己，啊哦。。。

#include<iostream> using namespace std; const int N = 1003; int a[N]; int main() { int n; while(cin>>n) { for(int i=0;i<n;i++) { cin>>a[i]; } int ans=-1; for(int i=0;i<n;i++) { int low=a[i]; for(int j=i;j<n;j++) { if(low>a[j]) low=a[j]; int tmp=(j-i+1)*low; if(tmp>ans) ans=tmp; } } cout<<ans<<endl; } }

遍历所有的直方图，对于每一个i，都向后寻找，直到找到比当前矩形i低的矩形j，这时候计算从i到j的面积，如果比之前的面积大，就更新。

注：ccf第三题，不是模拟，可能每一年情况不一样，况且2013年的题目有点早了，属于特例吧。。。