区间dp，，，我不会啊，，dp好久没做了。
区间dp是用来处理相邻合并继承的问题的，例如本题，相邻是条件。f[i][j]中i，j一般是区间左右端点。可以表示还剩这个区间时最大价值（例如本题），所以最后列举的是长度为一的区间。但大多数是表示此区间已处理时的最大值。一般一维循环枚举len长度，一维枚举左端点，手算右端点。也可以枚举左右端点。
#include <iostream> #include <cstdio> using namespace std; int f[2011][2011],a[2011],n,maxn; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++){ for(int j=n;j>=i;j--){ f[i][j]=max(f[i-1][j]+(n-j+i-1)*a[i-1],f[i][j]); f[i][j]=max(f[i][j+1]+(n-j+i-1)*a[j+1],f[i][j]); } } for(int i=1;i<=n;i++) maxn=max(maxn,f[i][i]+n*a[i]); printf("%d",maxn); return 0; }
P2858 [USACO06FEB]奶牛零食Treats for the Cows
原文：https://www.cnblogs.com/jindui/p/11335905.html
