专栏文章

题解：P2135 方块消除

DDiaoHantong
P2135题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqyrck8
此快照首次捕获于
2025/12/04 12:56
3 个月前
此快照最后确认于
2025/12/04 12:56
3 个月前
查看原文

题目传送门

思路

这道题一看就是区间DP，每消除一个区域的方块，就可以得到 bi2b_i^2 的分数，假设 fi,jf_{i,j} 为消除区间 [i,j][i,j] 的最高分，那么，对于区域 jj ，就有两种决策：
决策1：消除区域 jj，那么 fi,j=fi,j−1+bi2f_{i,j}=f_{i,j-1}+b^2_i
决策2：暂时不消除区域 jj,与之前的某个同色块连在一起消除，但对于决策2，我们需要清楚知道区间 [i,j−1][i,j-1] 中每一个区域的消除情况，状态数过多，我们可以换一种思路。
决策2会对未来行动产生影响，所以我们可以再加一个维度来假设未来情况。
设 fi,j,kf_{i,j,k} 表示消除区间 [i,j][i,j] 且区域 jj 之后有 kk 个与区域 jj 同色的方块的最大得分，对于区域 jj，有以下两种决策：
决策1：消除区域 jj 和与之相连的 kk 个同色方块，那么 fi,j,k=fi−1,j−1,0+(bj+k)2f_{i,j,k}=f_{i-1,j-1,0}+(b_j+k)^2。
决策2：暂时不消除区域 jj 区域，与之前的某个同色区域连在一起消除。假设区间 [i,j−1][i,j-1] 中与区域 jj 同色的区域所在位置为 pp，那么 fi,j,k=fi,p,k+bj+fp+1,j−1,0f_{i,j,k}=f_{i,p,k+b_j}+f_{p+1,j-1,0} 。
综上所述，
fi,j,k=max⁡(fi−1,j−1,0+(bj+k)2,fi,p,k+bj+fp+1,j−1,0)f_{i,j,k}=\max(f_{i-1,j-1,0}+(b_j+k)^2,f_{i,p,k+b_j}+f_{p+1,j-1,0})。
边界为 fi,j,k=0,fi,i,k=(bi+k)2f_{i,j,k}=0,f_{i,i,k}=(b_i+k)^2 ,
即消除区间 [i,i][i,i] 的方块且区域 ii 之后有 kk 个与区域 ii 同色的方案最大得分为 (bi+k)2(b_i+k)^2。
目标解为 f1,n,0f_{1,n,0} ,即消除区域 [1,n][1,n] 的方块且区域 nn 后有 00 个与区域 nn 同色的方块的最大得分。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int c[55],b[55];
long long f[55][55][1005];
//f[i][j][k]代表消除区间[i,j]的方块且区域j之后(未来)有k个与区域j同色的方块的最大得分
int main(){
    int n,s=0;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++)cin>>b[i],s+=b[i];
    for(int len=1;len<=n;len++){//枚举阶段
        for(int i=1;i+len-1<=n;i++){//枚举状态
            int j=i+len-1;
            for(int k=0;k<=s;k++){//决策1
                f[i][j][k]=max(f[i][j][k],f[i][j-1][0]+(b[j]+k)*(b[j]+k));
            }
            for(int p=i;p<j-1;p++){//决策2
                if(c[p]==c[j]){
                    for(int k=0;k<=s;k++){
                        f[i][j][k]=max(f[i][j][k],f[i][p][k+b[j]]+f[p+1][j-1][0]);
                    }
                }
            }
        }
    }
    cout<<f[1][n][0];//输出目标解f[1][n][0];
    return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...