- //dp[i][j] 表示第 i 次从左边取, 第 j 次从右边取的价值, 所以我们可以得到状态方程
- //dp[i][j]=max(dp[i-1][j]+(i+j)*a[i],dp[i][j-1]+(i+j)*a[n-j+1]) (i> 0 && j> 0 )
- //dp[i][0]=dp[i-1][0]+i*a[i],dp[0][i] dp[0][i-1]+i*a[n-i+1];
- #include<cstdio>
- #include<cmath>
- #include<string>
- #include<cstring>
- #include<iostream>
- using namespace std;
- typedef long long ll;
- const int inf=0x3f3f3f3f;
- const int maxn=2e3+10;
- int a[maxn];
- ll dp[maxn][maxn];
- int main()
- {
- int n;
- cin>>n;
- for(int i=1;i<=n;++i)
- cin>>a[i];
- ll ans=0;
- dp[0][0]=0;
- for(int i=1;i<=n;++i)
- {
- dp[i][0]=dp[i-1][0]+a[i]*i;
- dp[0][i]=dp[0][i-1]+a[n-i+1]*i;
- ans=max(ans,dp[i][0]);
- ans=max(ans,dp[0][i]);
- }
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j + i <= n; ++j)
- {
- dp[i][j]=max(dp[i-1][j]+(i+j)*a[i],dp[i][j-1]+(i+j)*a[n-j+1]);
- ans=max(ans, dp[i][j]);
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3397253.html