POJ3186 Treats for the Cows

2017年8月13日

给你一个含有n个数的队列,每次只能从队头或者队尾取出一个数,将第i次取出的数乘i,把所得结果都加起来,求取完所有的数能得到的最大值.

区间DP,定义 dp[i][j]表示队列中区间为[i, j]所能得到的最大值,而这个区间的得来,可以从 dp[i + 1][j],以及 dp[i][j - 1],那么就可以得到状态转移方程:

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

最后输出 dp[1][n] 即为所求.

链接:http://poj.org/problem?id=3186

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2005;
int a[N], dp[N][N];
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", a + i);
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i; j <= n; j++) {
            dp[i][j] = max(dp[i + 1][j] + a[i] * (n - j + i), dp[i][j - 1] + a[j] * (n - j + i));
        }
    }
    printf("%d\n", dp[1][n]);
    return 0;
}
去打赏

您的支持将鼓励我们继续创作!

[微信] 扫描二维码打赏

[支付宝] 扫描二维码打赏

One thought on “POJ3186 Treats for the Cows

Comments are closed.