【CF607B】Zuma——区间dp（记忆化搜索/递推）

以下是从中文翻译成人话的题面：

　　给定一个长度小于等于500的序列，每个数字代表一个颜色，每次可以消掉一个回文串，问最多消几次可以消完？

（7.16）

　　这个题从洛谷pend回来以后显示有103个测试点（满屏的AC好爽……

　　上午考试的时候这个题直接用马拉车暴力贪心骗了十五分。然而每次消掉一个最长的回文串并不一定是最优的策略，这道题要用DP来做。

　　设计状态f[l, r]表示消掉原串这段区间内串的最小代价。老师说直接递推不好搞，应该是因为这个循环的阶段不好确定。考虑用记忆化搜索来转移。

　　四种情况：

　　1、l = r，直接return 1；

　　2、[l, r]是回文的，return 1；

　　3、s[l] == s[r]，转移表示为update(f[l, r], f[l + 1][r - 1])；

　　　　这是因为我们可以在进行[l + 1, r - 1]的最后一次操作时顺手把两端消掉。

　　4、一般情况：枚举每个中间点mid，取分成的两个区间代价和的最小值。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#define maxn 510
using namespace std;
void open_file(string s) {
    string In = s + ".in", Out = s + ".out";
    freopen(In.c_str(), "r", stdin);
    freopen(Out.c_str(), "w", stdout);
}
int f[maxn][maxn], s[maxn], n;
int dfs(int l, int r) {
    if (l == r)
        return 1;
    if (f[l][r])
        return f[l][r];
    bool flag = 1;
    for (int i = l; i <= (l + r) >> 1; ++i)
        if (s[i] != s[r - i + l]) flag = false;
    int ans = (int)1e9;
    if (flag)
        return f[l][r] = 1;
    if (s[l] == s[r])
        ans = dfs(l + 1, r - 1);
    for (int i = l; i < r; ++i)
        ans = min(ans, dfs(l, i) + dfs(i + 1, r));
    return f[l][r] = ans;
}
int main() {
    open_file("zuma");
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> s[i];
    cout << dfs(1, n);
    return 0;
}

 ------------------------------------------------------------------------------

（7.17）其实这道题是可以直接递推的，阶段按照区间长度由短到长推进。（好像更好写……老师的话不能全信）

#include <cstdio>
#include <iostream>
#include <cstring>
#define maxn 510
using namespace std;
void open_file(string s) {
    string In = s + ".in", Out = s + ".out";
    freopen(In.c_str(), "r", stdin);
    freopen(Out.c_str(), "w", stdout);
}
int f[maxn][maxn], s[maxn], n;
void dp() {
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; ++i)
        f[i][i] = 1;
    for (int k = 2; k <= n; ++k)
        for (int l = 1, r = k; r <= n; ++l, ++r) {
            bool flag = 1;
            for (int i = l; i <= (l + r) >> 1; ++i)
                if (s[i] != s[r - i + l]) flag = false;
            if (flag) {
                f[l][r] = 1;
                continue;
            }
            if (s[l] == s[r])
                f[l][r] = f[l + 1][r - 1];
            for (int i = l; i < r; ++i)
                f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]);
        }
}
int main() {
    open_file("zuma");
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> s[i];
    dp();
    cout << f[1][n];
    return 0;
}

话说这个题的文件打开方式是从luogu学来的，整理成了一个接受文件名的函数。