~~~~

这三道DP题是逐层递进的，大家可以从前往后做。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1506

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

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

~~~~

1506：

分别找每一块板子的可以的最左边界和最右边界，注意这时不能用两个for暴力（显然会TLE），所以要用DP的思想边搜边保存。

另外注意的是要用long long.

#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 111111
#define ll __int64
using namespace std;

struct node
{
    int l,r;
    ll h;   //~~
}q[N];

int main()
{
    int n;
    while(~scanf("%d",&n),n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%I64d",&q[i].h);
            q[i].l=q[i].r=i;
        }
        q[0].h=q[n+1].h=-1;
        for(int i=2;i<=n;i++)   //左边界
            while(q[i].h<=q[q[i].l-1].h) q[i].l=q[q[i].l-1].l;
        for(int i=n-1;i>0;i--)  //右边界
            while(q[i].h<=q[q[i].r+1].h) q[i].r=q[q[i].r+1].r;
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans=max(q[i].h*(q[i].r-q[i].l+1),ans); //高度*区间长即得结果
        printf("%I64d\n",ans);
    }
    return 0;
}

~~~~

HDU 1505:

相对1506来说，1505只是需要多加一步逐层计算便可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define N 1111
#define INF
using namespace std;

int g[N][N],l[N],r[N],v[N];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                char c[5];
                scanf("%s",c);
                if(c[0]=='R') g[i][j]=0;   
                else g[i][j]=1;
            }
        }
        int ans=-1;
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(g[i][j]) v[j]++;     //~~
                else v[j]=0;        //~~
                l[j]=r[j]=j;
            }
            v[0]=v[m+1]=-1;
            for(int j=2;j<=m;j++)
                while(v[j]<=v[l[j]-1]) l[j]=l[l[j]-1];
            for(int j=m-1;j>0;j--)
                while(v[j]<=v[r[j]+1]) r[j]=r[r[j]+1];
            for(int j=1;j<=m;j++)
            {
                int res=v[j]*(r[j]-l[j]+1);
                ans=max(ans,res);
            }
        }
        printf("%d\n",ans*3);
    }
    return 0;
}

2870：

a,w,y,z一组，b,w,x,z一组，c,x,y,z一组，分别转换为a,b,c,就是1505的问题了。三次DP操作即可。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#define N 1111
using namespace std;

int n,m,ans;
int l[N],r[N];
int g[N][N];
char str[N][N];
void dp()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            l[j]=r[j]=j;
        g[i][0]=g[i][m+1]=-1;
        for(int j=2;j<=m;j++)
            while(g[i][j]<=g[i][l[j]-1]) l[j]=l[l[j]-1];
        for(int j=m-1;j>0;j--)
            while(g[i][j]<=g[i][r[j]+1]) r[j]=r[r[j]+1];
        for(int j=1;j<=m;j++)
            ans=max(ans,g[i][j]*(r[j]-l[j]+1));
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        ans=-1;
        for(int i=1;i<=n;i++)
            scanf("%s",str[i]+1);//~~
        memset(g,0,sizeof(g));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(str[i][j]=='a'||str[i][j]=='w'||str[i][j]=='y'||str[i][j]=='z')
                    g[i][j]=g[i-1][j]+1;//~~
                else
                    g[i][j]=0;  //~~
        dp();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(str[i][j]=='b'||str[i][j]=='w'||str[i][j]=='x'||str[i][j]=='z')
                    g[i][j]=g[i-1][j]+1;
                else
                    g[i][j]=0;
        dp();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                if(str[i][j]=='c'||str[i][j]=='y'||str[i][j]=='x'||str[i][j]=='z')
                    g[i][j]=g[i-1][j]+1;
                else
                    g[i][j]=0;
        dp();
        printf("%d\n",ans);
    }
    return 0;
}