搜索
您的当前位置:首页正文

poj3186(Treats for the Cows 基础区间dp 从两端取出顺序)

来源:独旅网


dp[ i ][ j ]:表示在区间[ i , j ](j>=i) 里可以获得的最大值。

如果我们从里往外进行计算,找一个数以他作为最后取出来的,由题意可以知道区间[ i , j ]只可能由区间 a[ i ] + [ i+1,j ]或者 [ i , j-1 ] +a[ j ]组成,结合题意.

dp[i][j]=max(dp[i][j-1]+a[j]*(n-(j-i)),dp[i+1][j]+a[i] *(n-(j-i)));

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2e3+5;
int a[N],dp[N][N];
int main(){
//    freopen("input.txt","r",stdin);
    int n;scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);//dp[i][j]=max(dp[i][j-1]+a[j]*(n-(j-i)),dp[i+1][j]+a[i]*(n-(j-i)));
    for(int i=n;i>=1;--i)
        for(int j=i;j<=n;++j)
            dp[i][j]=max(dp[i][j-1]+a[j]*(n-(j-i)),dp[i+1][j]+a[i]*(n-(j-i)));
    printf("%d\n",dp[1][n]);
}

因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top