详见代码
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 using namespace std; 5 int a[2010]; 6 int dp[2010][2010];//i到j的最大和是多少 7 int main() { 8 // freopen("in.txt","r",stdin); 9 int t; 10 while(~scanf("%d",&t)) { 11 for(int i=1; i<=t; i++) { 12 scanf("%d",&a[i]); 13 } 14 memset(dp,0,sizeof(dp)); 15 for(int i=t; i>=1; i--) {//逆序访问，顺序不行 16 for(int j=i; j<=t; j++) { 17 dp[i][j]=max(dp[i+1][j]+a[i]*(t+i-j),dp[i][j-1]+a[j]*(t+i-j));//状态转移方程 18 } 19 } 20 printf("%d ",dp[1][t]); 21 } 22 return 0; 23 }