Online Judge:P2135 方块消除 https://www.luogu.org/problem/P2135 (这题不用预处理)
Label: 区间 Dp
题目描述
Jimmy 最近迷上了一款叫做方块消除的游戏. 游戏规则如下: n 个带颜色方格排成一列, 相同颜色的方块连成一个区域(如果两个相邻方块颜色相同, 则这两个方块属于同一区域). 为简化题目, 将连起来的同一颜色方块的数目用一个数表示.
例如, 9 122233331 表示为
- 4 1 2 3 1
- 1 3 4 1
游戏时, 你可以任选一个区域消去. 设这个区域包含的方块数为 x, 则将得到 \(x^2\)个分值. 方块消去之后, 其余的方块就会竖直落到底部或其他方块上. 而且当有一列方块被完全消去时, 其右边的所有方块就会向左移一格. Jimmy 希望你能找出得最高分的最佳方案, 你能帮助他吗?
输入
第一行包含一个整数 m(1<=m<=50), 表示同颜色方块区域的数目. 第二行包含 m 个数, 表示每个方块的颜色(1 到 m 之间的整数).
输出
仅一个整数, 即最高可能得分.
样例
- Input
- 4 1 2 3 1 1 3 4 1
- Output
- 29
题解
区间 dp.
难点在于你消除一块后, 它还会自动并上. 所以如果直接定义两维状态 \(f[l][r]\), 表示只考虑区间 \([l,r]\)能得到的最大收益, 必然 WA. 因为我当前区间 \([l,r]\)还可能会并上后面或前面的某一段, 而你只考虑区间 \([l,r]\)显然不全面.
定义状态 \(f[l][r][lx]\)表示, 我仍然只考虑区间 \([l,r]\), 但此时我知道有 \(lx\)个和 \(a[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 https://www.luogu.org/problem/UVA10559 ], 基本一样, 预处理一下每个块的颜色长度即可.
[Luogu2135] 方块消除[区间 Dp]
来源: http://www.bubuko.com/infodetail-3231429.html