AcWing 322. 消木块

2021-03-17 23:24

阅读：555

标签：wing space code stream printf cpp iostream main 注意

由于木块可以由一些木块的消除，使两边相同颜色的合并
所以我们设定一个归并方式，即每个区间记录一下右边的延展性。
（等于左边找右边）
设 \(f[i][j][k]\) 为\([i, j]\) 区间，右侧有 \(k\) 个颜色 \(= a[j]\) 的。

考虑两种转移方式。
第一种操作：直接搞掉右边的。
设 \(i ，且 \([p, j]\) 区间内的颜色都是 \(a[j]\)。
那么把右边的搞掉即可，
\(f[i][p - 1][0] + (k + j - p + 1) ^ 2\)

第二种操作：考虑把 \([q + 1, p - 1]\) 这段搞掉，然后左边和右边的合并。

即找一个位置 \(i ; 且满足 \(a[q] = a[j]\)
\(f[q + 1][p - 1][0] + f[i][q][k + j - p + 1]\)
一个剪枝，保证 \(a[q] \not= a[q + 1]\)，否则肯定不优。

值得注意的是边界问题

#include 
#include 
#include 
using namespace std;
const int N = 205;
int n, a[N], f[N][N][N];
int dp(int l, int r, int k) {
    if (f[l][r][k] != -1) return f[l][r][k];
    int &v = f[l][r][k];
    if (l == r) return v = (k + 1) * (k + 1);
    int p = r;
    while (p - 1 >= l && a[p - 1] == a[r]) p--;
    v = (p == l ? 0 : dp(l, p - 1, 0)) + (k + r - p + 1) * (k + r - p + 1);
    for (int q = l; q

AcWing 322. 消木块

标签：wing space code stream printf cpp iostream main 注意

原文地址：https://www.cnblogs.com/dmoransky/p/12380412.html

上一篇：BOM-Window窗口对象

下一篇：windows安装sourceTree

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 322. 消木块
文章链接：http://soscw.com/index.php/essay/65517.html

亲，登录后才可以留言！

AcWing 322. 消木块

评论

热门文章

推荐文章

最新文章

置顶文章