题目描述
Jimmy最近迷上了一款叫做方块消除的游戏。游戏规则如下:n个带颜色方格排成一列,相同颜色的方块连成一个区域(如果两个相邻方块颜色相同,则这两个方块属于同一区域)。为简化题目,将连起来的同一颜色方块的数目用一个数表示。
例如,9 122233331表示为
4 1 2 3 1
1 3 4 1
游戏时,你可以任选一个区域消去。设这个区域包含的方块数为x,则将得到x^2个分值。方块消去之后,其余的方块就会竖直落到底部或其他方块上。而且当有一列方块被完全消去时,其右边的所有方块就会向左移一格。Jimmy希望你能找出得最高分的最佳方案,你能帮助他吗?
输入格式
第一行包含一个整数m(1<=m<=50),表示同颜色方块区域的数目。第二行包含m个数,表示每个方块的颜色(1到m之间的整数)。
输出格式
仅一个整数,即最高可能得分。
输入输出样例
4
1 2 3 1
1 3 4 1
29
题解:
a[i]表示方块的种类数
b[i]表示方块的个数
s[i]表示前缀和
因为这题有L和R,所以考虑区间DP,然后看完题目玄学感觉像祖玛?
然而我们可以发现这不够,因为我们想让后面连在一起消除,所以我们还要维护一个后面有几个和a[r],一样的数,这样更好转移,dp[l][r][k]表示在l到r这段区间,后面有k个和a[r]一样的数,全部删掉后的最大得分,这样我们就想办法把他们一起消除使得分最高。
先是我们为他们赋值。
枚举k(0~s[n]-s[r])//剩下一共s[n]-s[r]个数
dp[l][r][k]=dp[l][r-1][0]+(b[r]+k)*(b[r]+k)
然后枚举k(分割点a[k]==a[r])
j(0~s[n]-s[r] ) ])
dp[l][r][k]=max(dp[l][r][k],dp[l][k][b[r]+j]+dp[k+1][r-1][0].
1 #include<iostream>
2 using namespace std;
3 int n;
4 const int maxn=1e6+10;
5 int a[maxn];
6 int b[maxn];
7 int dp[100][100][100];
8 int s[maxn];
9 int main()
10 {
11 cin>>n;
12 for(int i=1;i<=n;i++)
13 {
14 cin>>a[i];
15 }
16 for(int i=1;i<=n;i++)
17 {
18 cin>>b[i];
19 s[i]=s[i-1]+b[i];
20 }
21 for(int i=0;i<=n;i++)
22 {
23 for(int l=1;l<=n;l++)
24 {
25 int r=l+i;
26 if(i+l>n)
27 {
28 break;
29 }
30 for(int k=0;k<=s[n]-s[r];k++)
31 {
32 dp[l][r][k]=dp[l][r-1][0]+(b[r]+k)*(b[r]+k);
33 }
34 for(int k=l;k<r;k++)
35 {
36 for(int j=0;j<=s[n]-s[r];j++)
37 {
38 if(a[k]==a[r])
39 {
40 dp[l][r][j]=max(dp[l][r][j],dp[l][k][b[r]+j]+dp[k+1][r-1][0]);
41 }
42 }
43 }
44 }
45 }
46 cout<<dp[1][n][0]<<endl;
47 return 0;
48 }