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

时间：2022-02-20 14:32:29

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

　　给定一个长度小于等于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，取分成的两个区间代价和的最小值。

代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #define maxn 510
  5. using namespace std;
  6. void open_file(string s) {
  7. string In = s + ".in", Out = s + ".out";
  8. freopen(In.c_str(), "r", stdin);
  9. freopen(Out.c_str(), "w", stdout);
  10. }
  11. int f[maxn][maxn], s[maxn], n;
  12. int dfs(int l, int r) {
  13. if (l == r)
  14. return 1;
  15. if (f[l][r])
  16. return f[l][r];
  17. bool flag = 1;
  18. for (int i = l; i <= (l + r) >> 1; ++i)
  19. if (s[i] != s[r - i + l]) flag = false;
  20. int ans = (int)1e9;
  21. if (flag)
  22. return f[l][r] = 1;
  23. if (s[l] == s[r])
  24. ans = dfs(l + 1, r - 1);
  25. for (int i = l; i < r; ++i)
  26. ans = min(ans, dfs(l, i) + dfs(i + 1, r));
  27. return f[l][r] = ans;
  28. }
  29. int main() {
  30. open_file("zuma");
  31. ios::sync_with_stdio(0);
  32. cin >> n;
  33. for (int i = 1; i <= n; ++i)
  34. cin >> s[i];
  35. cout << dfs(1, n);
  36. return 0;
  37. }

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

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

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #define maxn 510
  5. using namespace std;
  6. void open_file(string s) {
  7. string In = s + ".in", Out = s + ".out";
  8. freopen(In.c_str(), "r", stdin);
  9. freopen(Out.c_str(), "w", stdout);
  10. }
  11. int f[maxn][maxn], s[maxn], n;
  12. void dp() {
  13. memset(f, 0x3f, sizeof(f));
  14. for (int i = 1; i <= n; ++i)
  15. f[i][i] = 1;
  16. for (int k = 2; k <= n; ++k)
  17. for (int l = 1, r = k; r <= n; ++l, ++r) {
  18. bool flag = 1;
  19. for (int i = l; i <= (l + r) >> 1; ++i)
  20. if (s[i] != s[r - i + l]) flag = false;
  21. if (flag) {
  22. f[l][r] = 1;
  23. continue;
  24. }
  25. if (s[l] == s[r])
  26. f[l][r] = f[l + 1][r - 1];
  27. for (int i = l; i < r; ++i)
  28. f[l][r] = min(f[l][r], f[l][i] + f[i + 1][r]);
  29. }
  30. }
  31. int main() {
  32. open_file("zuma");
  33. ios::sync_with_stdio(0);
  34. cin >> n;
  35. for (int i = 1; i <= n; ++i)
  36. cin >> s[i];
  37. dp();
  38. cout << f[1][n];
  39. return 0;
  40. }

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

相关文章