洛谷 P2858 [USACO06FEB]奶牛零食Treats for the Cows

题目传送门

解题思路:

f[i][j]表示区间i~j可获得的最大利润,则每个区间可能从两个状态转移过来,即我上一次卖了第i-1个或第j+1个.

AC代码:

#include<iostream>
#include<cstdio>

using namespace std;

int n,v[2001],f[2001][2001],ans;

int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n; i++)
        scanf("%d",&v[i]);
    for(int i = 1;i <= n; i++)
        for(int j = n;j >= i; j--) {
            f[i][j] = max(f[i][j],f[i-1][j] + v[i-1] * (n - j + i - 1));
            f[i][j] = max(f[i][j],f[i][j+1] + v[j+1] * (n - j + i - 1));
        }
    for(int i = 1;i <= n; i++)
        ans = max(ans,f[i][i] + v[i] * n);
    printf("%d",ans);
    return 0;
}