题解 P2135 【方块消除】

· · 题解

blog更好的阅读体验

区间dp。

难点在于你消除一块后，它还会自动并上。所以如果直接定义两维状态f[l][r]，表示只考虑区间[l,r]能得到的最大收益，必然WA。因为当前区间[l,r]还可能会并上后面或前面的某一段，而你只考虑区间[l,r]显然不全面。

定义状态f[l][r][lx]表示，仍然只考虑区间[l,r]，但此时我知道有lx个和co[r]相同颜色的块接在r后面，该种情况下能得到的最大收益。

对于当前状态[l,r,lx]有如下几种决策：

决策一

直接炸掉r+lx这段，收益=f[l][r-1][0]+(len[r]+lx)^2。

决策二

分段处理，将区间分成两部分，每部分单独考虑贡献，然后相加。

在[l,r-1]中找一个与r相同颜色的坐标k，将区间分为[l,k]和[k+1,r-1]，此时两个子状态分别为{l,k,len[r]+lx}，{k+1,r-1,0}。其实意义就是先炸[k+1,r-1]这段，然后把后面那一坨移到k右边。

特殊地，当l==r时，直接返回(len[r]+lx)^2。

具体转移可以采用记搜方式，代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=205;
int f[N][N][N],a[N];
int co[N],len[N];
int solve(int l,int r,int lx){
    int all=len[r]+lx;
    if(l==r)return all*all;
    if(~f[l][r][lx])return f[l][r][lx];
    int res=solve(l,r-1,0)+all*all;
    for(int k=l;k<r;k++){
        if(co[k]==co[r])res=max(res,solve(k+1,r-1,0)+solve(l,k,all));
    }
    return f[l][r][lx]=res;
}
int main(){
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&co[i]);
    for(int i=1;i<=n;i++)scanf("%d",&len[i]);
    memset(f,-1,sizeof(f));
    printf("%d\n",solve(1,n,0));
}

upd

双倍经验[UVA10559 Blocks]，基本一样，预处理一下每个块的颜色长度即可。