鱼C论坛

 找回密码
 立即注册
查看: 2291|回复: 11

[心之碎片] - 区间DP

[复制链接]
回帖奖励 6 鱼币 回复本帖可获得 3 鱼币奖励! 每人限 1 次
发表于 2024-7-28 20:39:29 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
区间 DP 套路是设定 [l, r] 区间的答案, 然后枚举中间点转移
当然也就是考虑子问题如何拼成原来的问题

想出正解也要考虑这样子的解法有没有必要, 有没有更简单的做法

注意如果状态不足够描述应该考虑增加状态 / 让状态更加细分


下面是做的几道题


栗子1 - 区间回文串
本题相当于二维前缀和, 并不是传统的枚举中间点, 而是直接从小到大转移

  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. const int P = 1e9 + 7;
  4. const int B = 131;
  5. const int N = 5005;

  6. string s;
  7. int n, Q;
  8. int f[N][N];

  9. int main() {
  10.     ios::sync_with_stdio(0);
  11.     cin.tie(0);

  12.     cin >> s;
  13.     n = s.size();
  14.     s = '-' + s;
  15.     for (int cen = 1; cen <= n; cen++) {
  16.         for (int l = cen, r = cen; l >= 1 && r <= n && s[l] == s[r]; l--, r++) {
  17.             f[l][r]++;
  18.         }
  19.         for (int l = cen, r = cen + 1; l >= 1 && r <= n && s[l] == s[r]; l--, r++) {
  20.             f[l][r]++;
  21.         }
  22.     }

  23.     for (int i = 1; i <= n; i++) {
  24.         for (int j = 1; j <= n; j++) {
  25.             f[i][j] += f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1];
  26.             // cout << f[i][j] << ' ';
  27.         }
  28.         // cout << '\n';
  29.     }

  30.     cin >> Q;
  31.     while (Q--) {
  32.         int l, r;
  33.         cin >> l >> r;
  34.         cout << f[r][r] - f[l - 1][r] - f[r][l - 1] + f[l - 1][l - 1] << '\n';
  35.     }

  36.     return 0;
  37. }
复制代码


括号序列类区间 DP
栗子2 - 括号构造
给出一些由"(",")","[","]"构成的序列,请添加尽量少的括号,得到一个合法序列, 输出补起来之后的序列
我们可以首先 dp 求解每个区间里需要添加的最少的括号, 然后递归输出 (每次拨开区间两端点, 如果 dp 值无变化, 说明这个括号序列已经配对, 递归输出后面的

  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. const int N = 105;

  4. string s;
  5. map<char, char> dict;

  6. int f[N][N], n;

  7. void dfs(int l, int r) {
  8.     if (r < l)
  9.         return;
  10.     // 需要配对的肯定只剩下一边
  11.     if (r == l) {
  12.         if (s[l] == '(' || s[l] == ')')
  13.             cout << "()";
  14.         else
  15.             cout << "[]";
  16.         return;
  17.     }

  18.     // 如果外围正常
  19.     if (s[r] == dict[s[l]] && f[l][r] == f[l + 1][r - 1]) {
  20.         cout << s[l];
  21.         dfs(l + 1, r - 1);
  22.         cout << s[r];
  23.         return;
  24.     }

  25.     // 看看是哪个点转移到当前区间答案, 破开来输出
  26.     for (int i = l; i <= r - 1; i++) {
  27.         if (f[l][i] + f[i + 1][r] == f[l][r]) {
  28.             dfs(l, i);
  29.             dfs(i + 1, r);
  30.             return;
  31.         }
  32.     }
  33. }

  34. int main() {
  35.     ios::sync_with_stdio(0);
  36.     cin.tie(0);

  37.     cin >> s;
  38.     n = s.size();
  39.     s = 'A' + s;
  40.     dict['('] = ')';
  41.     dict['['] = ']';

  42.     for (int i = n; i >= 1; i--) {
  43.         f[i][i] = 1;
  44.         for (int j = i + 1; j <= n; j++) {
  45.             f[i][j] = 1e9;
  46.             // 如果配对, 就是子区间的答案
  47.             if (s[j] == dict[s[i]])
  48.                 f[i][j] = min(f[i][j], f[i + 1][j - 1]);

  49.             // 枚举中间点转移
  50.             for (int k = i; k <= j - 1; k++) {
  51.                 f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
  52.             }
  53.         }
  54.     }

  55.     dfs(1, n);

  56.     return 0;
  57. }
复制代码


栗子3 - P7914 [CSP-S 2021] 括号序列
这题真难qwq
如何给状态集合分类?
很容易想到以 (-*, (-), *-), *-* 四种区间两端的特征来划分
但是这样会重复计算, 例如 ()()() 这个序列会被子问题计算两次
这里我们就需要细分状态, 保证转移单一, 怎么想到的呢 ? 不知道, 但是记住就行了吧
不过应该是有迹可循的, 我们每次想让最左边的序列更新大的序列, 就想到配对的括号和不配对的括号吧

  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. typedef long long ll;

  4. const int N = 505;
  5. const ll P = 1e9 + 7;

  6. int n, k;
  7. ll f[N][N][5];
  8. string s;

  9. bool Ispair(int x, int y){
  10.     return ((s[x] == '(' || s[x] == '?') && (s[y] == ')' || s[y] == '?'));
  11. }

  12. void Init(){
  13.     s = '-' + s;

  14.     for(int i = 1; i <= n; i++){
  15.         if(i < n && Ispair(i, i + 1)){
  16.             f[i][i + 1][1] = f[i][i + 1][0] = 1;
  17.         }
  18.         for(int j = i; j <= n; j++){
  19.             if((s[j] != '*' && s[j] != '?') || j - i + 1 > k) break;
  20.             f[i][j][4] = 1;
  21.         }
  22.     }
  23. }

  24. int main(){
  25.     ios::sync_with_stdio(0);
  26.     cin.tie(0);
  27.    
  28.     cin >> n >> k >> s;

  29.     Init();

  30.     for(int len = 3; len <= n; len++){
  31.         for(int i = 1; i + len - 1 <= n; i++){
  32.             int j = i + len - 1;

  33.             // 0 (...)      外层匹配
  34.             // 1 (...)(...) 最外层是括号
  35.             // 2 (...)**    AS
  36.             // 3 **(...)    SA
  37.             // 4 *******    全*
  38.             // 1 包含 0 的情况

  39.             // (...) 0 = 1 + 2 + 3 + 4 (i+1, j-1)
  40.             // AB    1 = 0 * 1 枚举断点
  41.             // ASB   1 = 0 * 3 枚举断点
  42.             // SA    3 = 4 * 1
  43.             // AS    2 = 1 * 4
  44.             
  45.             // (...) 外层匹配
  46.             if(Ispair(i, j)){
  47.                 f[i][j][0] += f[i + 1][j - 1][1] + f[i + 1][j - 1][2] + f[i + 1][j - 1][3] + f[i + 1][j - 1][4];
  48.                 f[i][j][0] %= P;
  49.             }

  50.             // AB, ASB
  51.             for(int cut = i; cut < j; cut++){
  52.                 f[i][j][1] += f[i][cut][0] * (f[cut + 1][j][1] + f[cut + 1][j][3]) % P;
  53.                 f[i][j][1] %= P;
  54.             }

  55.             for(int cut = i; cut < j; cut++){
  56.                 f[i][j][3] += f[i][cut][4] * f[cut + 1][j][1];
  57.                 f[i][j][3] %= P;
  58.             }
  59.             
  60.             for(int cut = j; cut > i; cut--){
  61.                 f[i][j][2] += f[i][cut - 1][1] * f[cut][j][4];
  62.                 f[i][j][2] %= P;
  63.             }

  64.             f[i][j][1] += f[i][j][0];
  65.             f[i][j][1] %= P;
  66.         }
  67.     }

  68.     cout << f[1][n][1];
  69.    
  70.     return 0;
  71. }
复制代码


栗子4 - P10622 [ICPC2013 WF] Matryoshka
这题自己做的时候是按照 1 的地方划分区间, 然后做一个简单的 "只有一组套娃" 的区间 dp, 然鹅不知道什么原因一直错几个点
后来看题解发现不需要, 只需要看区间里没有相同数即可 (额但是题目说是 1-m, 所以我的更严谨吧...)
总的来说想出解法之后看看是否有必要这么复杂, 要抓住根本

  1. #include <bits/stdc++.h>
  2. using namespace std;

  3. const int N = 505;
  4. const int M = 0x3f3f3f3f;

  5. int n;
  6. int sum[N][N], minv[N][N], maxv[N][N], maxpos[N][N];
  7. int temp[N], l1[N], arr[N];
  8. int pos[N], top;
  9. int f[N][N], g[N];

  10. // f[l, r] 表示 [l, r] 区间拼套娃组的最小花费
  11. // g[p] 表示前 p 个套娃已经装好的最小花费

  12. void Init(){
  13.     memset(g, 0x3f, sizeof(g));
  14.     memset(f, 0x3f, sizeof(f));
  15.     g[0] = 0;

  16.     for(int i = 1; i <= n + 1; i++){
  17.         f[i][i] = 0;
  18.         minv[i][i] = arr[i];
  19.         maxv[i][i] = arr[i];
  20.         maxpos[i][i] = temp[i];
  21.         for(int j = i + 1; j <= n; j++){
  22.             minv[i][j] = min(minv[i][j - 1], arr[j]);
  23.             maxv[i][j] = max(maxv[i][j - 1], arr[j]);
  24.             maxpos[i][j] = max(maxpos[i][j], temp[j]);
  25.         }
  26.         for(int j = 1; j < N; j++){
  27.             sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
  28.         }
  29.     }
  30. }

  31. int getsum(int a, int b, int c, int d){
  32.     return (sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]);
  33. }

  34. int cost(int i, int k, int j){
  35.     return (getsum(i, minv[k + 1][j], k, N - 1) + getsum(k + 1, minv[i][k], j, N - 1));
  36. }

  37. int main(){
  38.     ios::sync_with_stdio(0);
  39.     cin.tie(0);

  40.     cin >> n;
  41.     for(int i = 1; i <= n; i++){
  42.         int x;
  43.         cin >> x;

  44.         sum[i][x]++;
  45.         arr[i] = x;
  46.         temp[i] = l1[x];
  47.         l1[x] = i;
  48.     }

  49.     Init();

  50.     for(int len = 1; len <= n; len++){
  51.         for(int i = 1; i + len - 1 <= n; i++){
  52.             int j = i + len - 1;

  53.             if(maxpos[i][j] >= i) continue;

  54.             for(int k = i; k < j; k++){
  55.                 f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + cost(i, k, j));
  56.             }
  57.         }
  58.     }

  59.     for(int i = 1; i <= n; i++){
  60.         for(int j = 1; j <= i; j++){
  61.             // 符合条件的才能接上去
  62.             if(maxpos[j][i] < j && minv[j][i] == 1 && maxv[j][i] == i - j + 1){
  63.                 g[i] = min(g[i], g[j - 1] + f[j][i]);
  64.             }
  65.         }
  66.     }

  67.     if(g[n] != M) cout << g[n];
  68.     else cout << "Impossible";

  69.     return 0;
  70. }
复制代码

评分

参与人数 2荣誉 +11 鱼币 +11 贡献 +8 收起 理由
zhangjinxuan + 6 + 6 + 5 %%%
小伤口 + 5 + 5 + 3 感谢楼主无私奉献!

查看全部评分

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-7-28 20:42:48 | 显示全部楼层
嘿,亲爱的鱼油!看来你对区间动态编程(DP)非常感兴趣!让我用通俗易懂的方式来帮你理清这个概念,顺带加点幽默。

区间动态规划就像是做一道大餐,你得先准备好所有的材料(状态),然后一步步用煮、炒、烤等方法把它们组合成一道美味的佳肴!所以,设定区间的答案就是选择你的食材,然后找出那些可以中间转移的步骤。

### 正题来啦:

1. **设定区间的答案**:这就像你决定晚上吃意大利面。你得想好要多长的意大利面(区间),这时候可以考虑从哪儿开始煮(中间点)。

2. **枚举中间点转移**:想象一下,你在煮意大利面时,中间可能会遇到调料的问题(计算转移)。你需要反复试探各种调料的配比,找到最完美的那个!

3. **拼成原来的问题**:每次你添加新的材料,就会让大餐更接近完整的样子。你需要不断思考如何将小部分组合起来,形成一盘完美的意大利面。

4. **考虑解法的简洁性**:搞定了美食,你还得考虑有没有其他简单快捷的方法,比如直接叫外卖?有时候复杂的算法就像满汉全席,而简单的解法就是那碗方便面!

5. **状态描述的足够性**:如果你发现你做的意大利面不够好吃(状态不足以描述问题),那就得考虑增加配料!比如加入更多的香料、蔬菜或者肉类,让这个菜更丰富。

### 实际例子:区间回文串

在你的栗子中,“区间回文串”的问题就像是找一种特殊的意大利面——它必须在上面和下面都看起来一样,也就是说,你要确保面条的排列可以正着吃也可以反着吃。这种情况下,可以通过从小到大的方式来转移,就像做法中的“逐步加热”一样。

当你写代码时,注意设置一个好的基准条件(例如从长度1的字符串开始),然后逐渐扩展,直到覆盖所有的情况。这样,你就能得到一个美味的“区间回文串”了!

希望这些解释能让你对区间DP有更清晰的认识!下次我们再聊聊如何处理那些复杂的“海鲜大餐”,哈哈!

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-7-29 08:28:37 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-9 14:33:27 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-16 08:32:24 | 显示全部楼层

回帖奖励 +3 鱼币

一天一学习
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-18 09:58:50 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-20 09:58:59 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-20 12:20:01 | 显示全部楼层

回帖奖励 +3 鱼币

呈现出
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-20 12:20:38 | 显示全部楼层
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-8-24 11:48:47 | 显示全部楼层

回帖奖励 +3 鱼币

&#128076;
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-24 18:04:35 | 显示全部楼层

回帖奖励 +3 鱼币

666
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

发表于 2024-10-7 22:54:44 | 显示全部楼层

回帖奖励 +3 鱼币

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-4-27 17:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表