HDU 1505 City Game-dp-（最大子矩陣模型）
分析：直接用最大字矩陣的公式做超時了。換個思路，這題跟上一題1506有關系，先以每層為底算出每個元素能到達的最大的高度，然後就跟1506一樣了。這裡求高度和求面積兩處地方用到了dp暫存數據。求高度用二重循環，然後每層為底求面積要二重循環加上外層就是三重循環，但是由於用了dp保存中間結果，所以這個三重循環不會超時。dp[j]表示當前層第j列能到達的最大的高度，狀態轉移：1.a[i][j]=='R'時，dp[j]=0；2.否則，若a[i-1][j]=='F'，則dp[j]++（這裡用到了dp，保存了前面層的數據，所以直接+1即可）；若a[i-1][j]=='R'，則dp[j]=1,。每層求面積的算法見1506題解
代碼：
#include
using namespace std;
int t,m,n;
int mx,sum;
int l[1005],r[1005],dp[1005];
char a[1005][1005];
int max(int i,int j)
{
return i>j?i:j;
}
void fir()//處理第一層
{
mx=0;
for(int j=0;j0&&dp[i]<=dp[t-1]) t=l[t-1];
l[i]=t;
}
for(int i=n-2;i>=0;i--){
int t=i;
while(t0&&dp[i]<=dp[t-1]) t=l[t-1];
l[i]=t;
}
for(int i=n-2;i>=0;i--){
int t=i;
while(t>t;
while(t--){
cin>>m>>n;
for(int i=0;i>a[i][j];
DP();
cout<
