跳跳跳跳跳

B

题意:
就是给你一个环,每个点有一个权值。

思考:
如果直接双指针的话,不知道哪里错了,一眼就能想到区间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的题目.

上一篇:C语言-函数的可变形参(不定形参)


下一篇:c语言,宏相关