[CSP-S模拟测试]:蛋糕（区间DP）

题目传送门（内部题34）

输入格式

第一行，一个正整数$n$。
第二行，$n$个正整数$a_i$，保证$a_i$互不相等。

输出格式

一行一个整数表示间宫卓司得到的蛋糕大小总和的最大值。

样例

样例输入1：

5
2 8 1 10 9

样例输出1：

样例输入2：

8
1 10 4 5 6 2 9 3

样例输出2：

数据范围与提示

样例1解释：

最优解为：卓司君选第$2$块；雨咲酱选第$1$块；卓司君选第$5$块；雨咲酱选第$4$块；卓司君选第$3$块。

数据范围：

对于$32\%$的数据，$1\leqslant n\leqslant 20$。
对于$64\%$的数据，$1\leqslant n\leqslant 30$。
对于$100\%$的数据，$1\leqslant n\leqslant 2,000,1\leqslant a_i\leqslant {10}^9$，保证$a_i$互不相等。

题解

考虑$DP$，定义$dp[i][j]$表示拿完还上的区间$[i,j]$的蛋糕大小之和的最大值，根据长度的奇偶判断该谁拿即可。

时间复杂度：$\Theta(n^2)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n;

long long a[2010];

long long dp[2010][2010];

long long ans;

int get(int x){if(x>n)x-=n;if(!x)x+=n;return x;}

long long DP(int l,int r,int x)

{

	if(x>=n-1)return 0;

	if(dp[l][r]!=-1)return dp[l][r];

	dp[l][r]=0;

	int ll=l,rr=r;

	int lft=get(l-1),rht=get(r+1);

	if(a[lft]>a[rht])l=lft;

	else r=rht;

	lft=get(l-1);

	rht=get(r+1);

	dp[ll][rr]=max(DP(lft,r,x+2)+a[lft],DP(l,rht,x+2)+a[rht]);

	return dp[ll][rr];

}

int main()

{

	memset(dp,-1,sizeof(dp));

	scanf("%d",&n);

	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

	for(int i=1;i<=n;i++)ans=max(ans,a[i]+DP(i,i,1));

	printf("%lld",ans);

	return 0;

}

rp++

巴特西