题意：有宽度相同高度不同的长方体挨着放在一起，求能构成的面积最大的长方体
分析：也是思维的转换。这题的主思路不是dp，dp只是起一个辅助作用。具体做法：枚举每个长方体，求以这个长方体的高度为高的最大的长方体面积，不断更新答案。用一个l[i]和r[i]数组表示第i个矩形的左右比它高的远的位置，，所以面积s=a[i]*(r[i]-l[i]+1).但是直接两重循环会超时，这时用了一点dp的思想，这里用的不是dp递推的思想，而是dp保存中间结果降低时间复杂度的思想。虽然也是两重循环，但是由于dp[]的关系，就跳过了很多重复的比较步骤。
注意积累这题的主思路，还有dp的用法。
代码：
#include<iostream>#include<cstring>using namespace std;long long n,a[100005];long long mx,sum;int l[100005],r[100005];long long max(long long i,long long j){return i>j?i:j;}void DP(){mx=0;for(int i=0;i<n;i++) l[i]=i,r[i]=i;for(int i=1;i<n;i++){int t=i;while(t>0&&a[t-1]>=a[i])t=l[t-1];l[i]=t;}for(int i=n-2;i>=0;i–){int t=i;while(t<n-1&&a[i]<=a[t+1])t=r[t+1];r[i]=t;}for(int i=0;i<n;i++){sum=a[i]*(r[i]-l[i]+1);mx=max(sum,mx); }}int main(){while(cin>>n){if(!n) break;for(int i=0;i<n;i++) cin>>a[i];DP();cout<<mx<<endl;}}
有时我们选择改变，并非经过深思熟虑，而更像是听见了天地间冥冥中的呼唤，
