[USACO06FEB]Treats for the Cows

分析

表示一共拿 块糖, 块从开头拿时的最大价值

#include<bits/stdc++.h>
using namespace std;
int n,a[2003],mx,f[2003][2003];// 一共拿 i 块糖,其中 j 块从开头拿
int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)f[i][i]=f[i-1][i-1]+a[i]*i,f[i][0]=f[i-1][0]+a[n-i+1]*i;

    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            f[i][j]=max(f[i-1][j]+a[n-i+1+j]*i,f[i-1][j-1]+a[j]*i);

    for(int i=0;i<=n;i++)mx=max(mx,f[n][i]);
    printf("%d",mx);
    return 0;
}

 上一篇
[NOIP2017] 矩阵取数游戏 [NOIP2017] 矩阵取数游戏
本来是很简单的区间 DP 结果还要加一个高精。。。 int128 走起 ```cppincludedefine int __int128using namespace std;const int N=82;int n,m,tot;int
2018.10.01
下一篇 
UVA437The Tower of Babylon UVA437The Tower of Babylon
UVA437The Tower of Babylon你可能已经听说过巴比伦塔的传说。现在这个传说的许多细节已经被遗忘。所以本着本场比赛的教育性质,我们现在会告诉你整个传说: 巴比伦人有 n 种长方形方块,每种有无限个,第 i 种方块的三边边
2018.10.01
  目录