题目描述

Jimmy最近迷上了一款叫做方块消除的游戏。游戏规则如下:n个带颜色方格排成一列,相同颜色的方块连成一个区域(如果两个相邻方块颜色相同,则这两个方块属于同一区域)。为简化题目,将连起来的同一颜色方块的数目用一个数表示。

例如,9 122233331表示为

4 1 2 3 1

1 3 4 1

游戏时,你可以任选一个区域消去。设这个区域包含的方块数为x,则将得到x^2个分值。方块消去之后,其余的方块就会竖直落到底部或其他方块上。而且当有一列方块被完全消去时,其右边的所有方块就会向左移一格。Jimmy希望你能找出得最高分的最佳方案,你能帮助他吗?

输入格式

第一行包含一个整数m(1<=m<=50),表示同颜色方块区域的数目。第二行包含m个数,表示每个方块的颜色(1到m之间的整数)。

输出格式

仅一个整数,即最高可能得分。

输入输出样例

输入 #1
4
1 2 3 1
1 3 4 1
输出 #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 }

 

01-12 08:01