对于基本区间dp，设dp[l][r]是区间l到r的最大价值。
我们可以枚举区间的长度，在枚举左端点，判断即可。
当右端点大于n，就break。
dp[l][r]=max(dp[l+1][r]+v[l]*(n-i+1),dp[l][r-1]+v[r]*(n-i+1))
别忘了初始化，dp[i][i]=n*v[i].
代码：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int dp[3000][3000]; 5 int n,v[3000]; 6 int main(){ 7 scanf("%d",&n); 8 for(int i=1;i<=n;++i) 9 scanf("%d",&v[i]); 10 for(int i=1;i<=n;++i)dp[i][i]=n*v[i]; 11 for(int i=2;i<=n;++i){ 12 for(int l=1;l<=n;l++){ 13 int r=l+i-1; 14 if(r>n)break; 15 dp[l][r]=max(dp[l+1][r]+v[l]*(n-i+1),dp[l][r-1]+v[r]*(n-i+1)); 16 } 17 }printf("%d\n",dp[1][n]); 18 return 0; 19 }
原文：https://www.cnblogs.com/h-lka/p/11146515.html
