题意:
就是给你一个环,每个点有一个权值。
思考:
如果直接双指针的话,不知道哪里错了,一眼就能想到区间dp,和之前的环的题很类似,就是枚举长度,然后dp从左边或者右边转移即可。
int T,n,m;
int va[N];
int dp[M][M];
signed main()
{
IOS;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>va[i];
va[i+n] = va[i];
dp[i][i] = dp[i+n][i+n] = va[i];
}
for(int len=2;len<=n;len++)
{
for(int l=1;l+len-1<=2*n;l++)
{
int r = l+len-1;
dp[l][r] = max(dp[l][r],max(dp[l+1][r]+va[l]*len,dp[l][r-1]+va[r]*len));
}
}
int maxn = 0;
for(int i=1;i<=n;i++) maxn = max(maxn,dp[i][i+n-1]);
cout<<maxn;
return 0;
}
总结:
多多理解和总结区间dp的题目.