hdoj 1506&&1505（City Game） dp

// l表示从l[i]到i连续大于a[i]的最远左区间。r表示从i到r[i]连续大于a[i]的最远又区间

DP 找出 a[i] 的最远左区间和最远右区间与自己连着的比自己大的数的长度 , 然后用这个长度乘以 a[i], 乘积最大的那个就是答案

hdoj 1506

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define N 100000+10

#define INF 0xfffffff

#define ll __int64

ll Max(ll x,ll y)

{

    if(x>y)

        return x;

    return y;

}

ll r[N],l[N];

ll a[N];

int main()

{

    ll n;

    while(scanf("%I64d",&n),n)

    {

        for(int i=1;i<=n;i++)

            scanf("%I64d",&a[i]);

        a[0]=a[n+1]=-INF;

        l[0]=r[n+1]=0;

        for(int i=1;i<=n;i++)

        {

                l[i]=i;

                while(a[l[i]-1]>=a[i])

                   l[i]=l[l[i]-1];

        }

        for(int i=n;i>=1;i--)

        {

                r[i]=i;

                while(a[r[i]+1]>=a[i])

                    r[i]=r[r[i]+1];

        }

        ll maxn=0;

        for(int i=1;i<=n;i++)

        {

            maxn=Max((r[i]-l[i]+1)*a[i],maxn);

        }

        printf("%I64d\n",maxn);

    }

    return 0;

}

hdoj 1505是1506的加强版，对于矩阵的每一行採取相同的操作

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

#define  N 1000+10

char a[N][N];

int dp[N][N];

int r[N],l[N];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

        int maxn=0;

        scanf("%d%d",&n,&m);

        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=m;j++)

                {

                    scanf(" %c",&a[i][j]);

                    if(a[i][j]=='R')

                        dp[i][j]=0;

                    else

                        dp[i][j]=dp[i-1][j]+1;

                }

        }

        for(int i=1;i<=n;i++)

        {

            dp[i][0]=dp[i][m+1]=-1;

            l[0]=r[m+1]=0;

            for(int j=1;j<=m;j++)

            {

                l[j]=j;

                while(dp[i][l[j]-1]>=dp[i][j])

                   l[j]=l[l[j]-1];

            }

            for(int j=m;j>=1;j--)

            {

                r[j]=j;

                while(dp[i][r[j]+1]>=dp[i][j])

                   r[j]=r[r[j]+1];

            }

            for(int j=1;j<=m;j++)

            {

                maxn=max(maxn,(r[j]-l[j]+1)*3*dp[i][j]);

            }

        }

        printf("%d\n",maxn);

    }

    return 0;

}