POJ 3186 Treats for the Cows

简单DP

dp[i][j]表示的是i到j这段区间获得的a[i]*(j-i)+... ...+a[j-1]*(n-1)+a[j]*n最大值

那么[i,j]这个区间的最大值肯定是由[i+1,j]与[i,j-1]区间加上端点的较大值推过来的。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=2000+10;
int dp[maxn][maxn];
int a[maxn];
int n;

int MAX(int a,int b)
{
    if(a>b) return a;
    return b;
}

int main()
{
    scanf("%d",&n);
    {
        for(int i=1; i<=n; i++) scanf("%lld",&a[i]);
        memset(dp,0,sizeof dp);
        int c=n;
        for(int i=1; i<=n; i++) dp[i][i]=a[i]*c;
        c--;
        int ans=0;
        for(int i=2; i<=n; i++) //区间长度
        {
            for(int j=1; j<=n; j++) //起点
            {
                int st=j,en=i+j-1;
                if(en>n) break;
                dp[st][en]=MAX(dp[st+1][en]+c*a[st],dp[st][en-1]+c*a[en]);
            }
            c--;
        }
        printf("%d
",dp[1][n]);
    }
    return 0;
}