【题目】UVA-10559 方块消除

题目大意

有$n$个带颜色的方块排成一排，相同颜色的方块连成一段同色区域，如下图所示： 游戏时，玩家可以任选一段同色区域，将其消去。设消去的这段包含$x$个相同颜色的方块，则此次消除操作的得分为$x^2$。然后右边的所有方块会往左边合拢。如下图所示： 对于给定的一排方块，计算消除它们能得到的最大得分。 原题目有$t$组数据（$t⩽15$），每组数据$n⩽200$。

---

思路

不知道为什么我们就定了一个状态$f[i][j][k]$。设第$i$个方块的颜色为$a[i]$，则$f[i][j][k]$表示区间$[l,r]$右侧有$k$个与$a[r]$同色的方块时，将区间$[l,r+k]$全部消除的最大得分。 转移分两种：

既然右侧有$k+1$个同色的方块，可以把区间$[l,r+k]$右侧所有同色方块找出来，一并消除。具体实现是找到尽可能长的与$a[r]$同色的区间$[p,r]$，消除的得分为$(r+k-p+1{)}^2$。 $$f[l][r][k]\leftarrow f[l][p-1][0]+(r+k-p+1{)}^2$$ 还有可能出现的情况是，一段区间被消除后，右边的方块恰好与左边的方块同色，合拢后构成了一段更长的同色区间。若$p$位置的左侧还有与$a[r]$同色的区间，就可能出现上述情况，于是我们讨论消除中间的哪一段区间。枚举同色区间的右端点$q$，考虑消除区间$[q+1,p-1]$中的所有方块。 $$f[i][j][k]\leftarrow f[l][q][r+k-p+1]+f[q+1][p-1][0]$$ 其实还有消除其中多段不同色区间的情况。设区间$[p,r+k]$左侧还有$w$个与$a[r]$同色的区间，右端点分别为$q_1,q_2,\dots ,q_w$。此时存在一种方案，把这些同色区间之间的不同色区间先全部消除，然后剩下的$w+1$个同色区间拼在一起一并消除。这种情况是包含在消除区间$[q_w+1,p-1]$的情况中的，此时最右边的两个同色区间合并，变成了状态$f[l][q_{w-1}][r+k-p+1]$，所以可以被讨论到。

推荐记忆化搜索实现。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200+5; int a[maxn],n,t,kase=0; int f[maxn][maxn][maxn]; bool vis[maxn][maxn][maxn]; int dp_dfs(int l,int r,int k){ if(l>r)return 0; if(vis[l][r][k])return f[l][r][k]; int q,p=r;vis[l][r][k]=1; while(p>l&&a[r]==a[p-1])p--; f[l][r][k]=dp_dfs(l,p-1,0)+(r+k-p+1)*(r+k-p+1); for(q=l;q<p;q++)if(a[q]==a[r]&&a[q]!=a[q+1]) f[l][r][k]=max(f[l][r][k],dp_dfs(l,q,r+k-p+1)+dp_dfs(q+1,p-1,0)); return f[l][r][k]; } int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)scanf("%d",&a[i]); printf("Case %d: %d\n",++kase,dp_dfs(1,n,0)); } return 0; }

思路$\times 2$

考试的时候考到原题了。。然而原来的状态推不动。。自己重新定了一个状态。。 首先可以定一个幼稚的状态：$f[i][j]$表示将区间$[i,j]$消除能得到的最大得分。答案为$f[1][n]$。 考虑到一些不可描述的因素，定义一个辅助状态$g[i][j][c]$，表示当$a[i]=a[j]$时，消除区间$[i,j]$内的一些方块，使得这一部分方块还剩下$c$个与$a[i]$同色的方块，能够得到的最大得分。 状态转移：

$$\begin{array}{rl}f[i][j]& =\max \{\begin{array}{ll}f[i][k]+f[k+1][j]& \\ g[i][j][c]+c^2& \text{if }a[i]=a[j]\end{array}\\ g[i][j][c]& =\max \{g[i][q][c-(j-p+1)]+f[q+1][p-1]\}\end{array}$$

第二个式子中$p,q$的含义跟标解相同。 偏不用记忆化搜索。

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=200+5; const int INF=0x3f3f3f3f; int a[maxn],n,t,kase=0; int f[maxn][maxn],g[maxn][maxn][maxn]; int main(){ scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++){ f[i][j]=-INF; for(int k=0;k<=j-i+1;k++)g[i][j][k]=-INF; } for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=n;i++)f[i][i]=1,g[i][i][1]=0; for(int t=2;t<=n;t++) for(int i=1,j;(j=i+t-1)<=n;i++){ for(int k=i;k<j;k++) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]); if(a[i]!=a[j])continue; int q,p=j,cnt=0; while(p>i&&a[p]==a[p-1])p--; if(p==i)f[i][j]=max(f[i][j],t*t),g[i][j][t]=0; else for(q=i;q<p;q++)if(a[q]==a[j]){ cnt++; if(a[q]!=a[q+1])for(int k=j-p+1;k<=j-p+1+cnt;k++) g[i][j][k]=max(g[i][j][k],g[i][q][k-(j-p+1)]+f[q+1][p-1]); } for(int k=0;k<=t;k++)f[i][j]=max(f[i][j],g[i][j][k]+k*k); } printf("Case %d: %d\n",++kase,f[1][n]); } return 0; }