POJ - 3186 Treats for the Cows（DP）

题目大意：给你一个数组，每次你可以取两个数中的一个进行操作，要么取数组的第一个，要么数组的最后一个(取完之后，该数删除)
假设取出来的数组组成了A
现在要求使Sum = A[1] * 1 + A[2] * 2 + A[3] * 3 … + A[n] * n达到最大

解题思路：用dp[i][j]表示前面取了i个，后面取了j个最大值
则转移方程dp[i][j] = max(dp[0][i + j - 1] * (i + j) * num[j], dp[1][i + j - 2] * (i + j - 1) * num[j - 1]。。。)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010;
#define ll long long

ll num[N], dp[N][N];
int n;

void init() {
    for (int i = 1; i <= n; i++)
        scanf("%lld", &num[i]);
}

void solve() {

    memset(dp, 0, sizeof(dp));
    dp[1][0] = num[1];
    dp[0][1] = num[n];

    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[j][i] = dp[j][i - 1] + num[n - i + 1] * i;
            }
            else if (j == i){
                dp[j][0] = dp[j - 1][0] + num[j] * i; 
            }
            else { 
                dp[j][i - j] = max(dp[j - 1][i - j] + num[j] * i, dp[j][i - j - 1] + num[n - i + j + 1] * i);
            }
        }
    ll ans = 0;
    for (int i = 0; i <= n; i++)
        ans = max(dp[i][n - i], ans);
    printf("%lld\n", ans);
}

int main() {
    while (scanf("%d" , &n) != EOF) {
        init();
        solve();
    }
    return 0;
}