学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1506

      一道写了很久的题，以前看过，都没什么感觉，今天终于把它搞懂了。很多人都说是DP，但我没感觉出来，好像就是YY题了。

      题目中叫求一个最大的区域，则第i个矩形对应的面积是ave[i] = (r[i] - l[i] + 1) * a[i];l[i]表示以它这个高度所能到达的最左边的位置（最左一个高度不小于它的高度的位置），而r[i]表示能到达的最右边的位置（最右一个高度不小于它的高度的位置）。

      那么这个题目就转到怎么求r[]和l[]上了。如果每次依次向左向右找，肯定会超时的。这时就会用到迭代了，比如说求a[i]的l[i]，如果a[i]大于a[i-1]那么l[i] = i，这个不难理解，不解释；如果a[i]小于a[i-1]，那么l[i]肯定小于l[i-1]，找l[i]就可以直接跳到l[i-1]的位置上，在往左去找了。

     #include <iostream><br /> using namespace std;</p> <p>__int64 a[100005];<br /> int r[100005];<br /> int l[100005];</p> <p>int main()<br /> {<br /> int n,i,k;<br /> while(scanf("%d",&n)!=EOF && n!=0)<br /> {<br /> scanf("%d",&a[1]);<br /> l[0] = 0;<br /> l[1] = 1;<br /> for(i=2;i<=n;i++)<br /> {<br /> scanf("%d",&a[i]);<br /> if(a[i] > a[i-1])<br /> l[i] = i;<br /> else<br /> {<br /> k = i;<br /> while(k--)<br /> {<br /> if(a[k] < a[i])<br /> {<br /> l[i] = k+1;<br /> break;<br /> }<br /> else<br /> {<br /> k = l[k];<br /> }<br /> }<br /> }<br /> }<br /> r[n] = n;<br /> for(i=n-1;i>=1;i--)<br /> {<br /> if(a[i] > a[i+1])<br /> r[i] = i;<br /> else<br /> {<br /> k = i;<br /> while((++k) != n+1)<br /> {<br /> if(a[k] < a[i])<br /> {<br /> r[i] = k-1;<br /> break;<br /> }<br /> else<br /> {<br /> k = r[k];<br /> }<br /> }<br /> if(k == n+1)<br /> r[i] = n;<br /> }<br /> }</p> <p> __int64 max = 0;<br /> for(i=1;i<=n;i++)<br /> {<br /> __int64 ave = (r[i] - l[i] + 1) * a[i];<br /> if(ave > max)<br /> max = ave;<br /> }<br /> printf("%I64d/n",max);<br /> }<br /> return 0;<br /> }