第一眼感觉是贪心，，果断WA。然后又设计了一个两个方向的dp方法，虽然觉得有点不对，但是过了样例，交了一发，还是WA，不知道为什么不对= =，感觉是dp的挺有道理的，，代码如下（WA的）：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int N = 2000 + 5; 6  7 int a[N]; 8 int dp[N][N]; 9 int n;10 11 int getDay(int i,int j)12 {13     return n - (j - i) + 1;14 }15 16 int main()17 {18     while(scanf("%d",&n) == 1)19     {20         for(int i=1;i<=n;i++) scanf("%d",a+i);21         memset(dp,0,sizeof dp);22         for(int i=1;i<=n;i++)23         {24             for(int j=i+1;j<=n+1;j++) dp[i][j] = max(dp[i][j], dp[i-1][j] + getDay(i,j) * a[i]);25         }26         for(int j=n+1;j>=1;j--)27         {28             for(int i=j-1;i>=0;i--) dp[i][j] = max(dp[i][j], dp[i][j+1] + getDay(i,j) * a[j]);29         }30         int ans = 0;31         for(int i=0;i<=n;i++) ans = max(ans, dp[i][i+1]);32         printf("%d\n",ans);33     }34     return 0;35 }
        
       
      

 

　　看了别人的博客以后，有一个不错的dp方法：dp[i][j]表示左边已经选了i个右边已经选了j个最大值，然后转移也很明显。AC代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int N = 2000 + 5; 6  7 int a[N]; 8 int dp[N][N]; 9 int n;10 11 int main()12 {13     while(scanf("%d",&n) == 1)14     {15         for(int i=1;i<=n;i++) scanf("%d",a+i);16         memset(dp,0,sizeof dp);17         for(int i=0;i<=n;i++)18         {19             for(int j=0;i+j<=n;j++)20             {21                 if(i > 0) dp[i][j] = max(dp[i][j], dp[i-1][j] + a[i] * (i+j));22                 if(j > 0) dp[i][j] = max(dp[i][j], dp[i][j-1] + a[n-j+1] * (i+j));23             }24         }25         int ans = 0;26         for(int i=0;i<=n;i++) ans = max(ans, dp[i][n-i]);27         printf("%d\n",ans);28     }29     return 0;30 }