本文主要是介绍hdu 1505 dp City Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
嗯。主要就是记录一行比a[i]的高度高的相邻的长度。然后比较面积最大的。
那么，怎么记录。。。
如果，a[i]左边第一个的高度比a[i]高，那么，搜寻比a[i-1]高的、、、依次类推。若果，a[i-1]<a[i]，那么a[i]到左边的高度就是它自己。
而当到a[i+1]的时候，如果a[i+1]<a[i]，这时候又要求比a[i]高的所有左边相邻的长度，又要重新再算一遍a[i]。。。
同理，右边一样这样计算与a[i]相邻的长度。
这时候，就用到了DP的思想。即所有的计算不会重复。计算过一遍之后，记录起来，用的时候，直接拿出来。
那么，用left[i]表示a[i]左边相邻的长度，right[i]表示右边的。初始化：left[i]=right[i]=i;
递推： a[i]<=a[left[i]-1] left[i]=left[left[i]-1]
a[i]>=a[right[i]+1] right[i]=right[right[i]+1]
#include <iostream>
using namespace std;int main()
{
// freopen("in.txt","r",stdin);int m,n;char ch;int t;int l[1005],r[1005];int a[1005]; //记录当前行的高度scanf("%d",&t);while(t--){ scanf("%d %d",&m,&n);int max=0;getchar();for(int i=0;i<m;i++){for(int j=0;j<n;j++)l[j]=r[j]=j;for(int j=0;j<n;j++){scanf(" %c ",&ch);if(i){if(ch=='R')a[j]=0;elsea[j]+=1;}elsea[j]=(ch=='R'?0:1);if(a[j])while(l[j]-1>=0&&a[l[j]-1]>=a[j])l[j]=l[l[j]-1]; }for(int j=n-1;j>=0;j--)if(a[j])while(r[j]+1<n&&a[r[j]+1]>=a[j])r[j]=r[r[j]+1];int ans;for(int j=0;j<n;j++)if(a[j]) {ans=(r[j]-l[j]+1)*a[j];if(ans>max)max=ans;}}printf("%d\n",max*3);}return 0;
}
这篇关于hdu 1505 dp City Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
