NO.90十六届蓝桥杯备战|动态规划-区间DP|回文字串|Treats for the Cows|石子合并|248(C++)

区间dp也是线性dp的⼀种，它⽤区间的左右端点来描述状态，通过⼩区间的解来推导出⼤区间的解。因此，区间DP的核⼼思想是将⼤区间划分为⼩区间，它的状态转移⽅程通常依赖于区间的划分点。
常⽤的划分点的⽅式有两个：

• 基于区间的左右端点，分情况讨论；
• 基于区间上某⼀点，划分成左右区间讨论

P1435 [IOI 2000] 回文字串 - 洛谷

先找重复⼦问题定义状态表⽰

• ⼤问题是让整个字符串[1, n]变成回⽂串的最⼩插⼊次数；
• 当我们发现这个字符串左右元素⼀样的时候，那就去看看[2, n - 1]变成回⽂的最⼩插⼊次数；
• 如果左右不相同，那么我们会在左边补上⼀个字符，或者右边补上⼀个字符，然后看看剩下区间的最⼩插⼊次数。
  因此，重复的⼦问题就是看看某个区间变成回⽂串的最⼩插⼊次数。

1. 状态表⽰：
   dp[i][j]表⽰：字符串[i, j]区间，变成回⽂串的最⼩插⼊次数。
   那么dp[1][n]就是我们要的结果。
2. 状态转移⽅程：
   根据区间的左右端点，分情况讨论：
   a. 如果s[i] = s[j] ：那我们就去看看[i + 1, j - 1]区间的最⼩插⼊次数，即dp[i + 1][j - 1] ；
   b. 如果s[i] = s[j] ：

• 要么去左边补⼀个s[j] ，此时的最⼩插⼊次数为dp[i][j - 1] + 1 ；
• 要么去右边补⼀个s[i] ，此时的最⼩插⼊次数为dp[i + 1][j] + 1 。
  因为要的是最⼩值，所以状态转移⽅程为min(dp[i + 1][j], dp[i][j - 1]) + 1 。

3. 初始化以及填表顺序：
   我们看dp 表
   

可以发现如下性质：

• ⽩⾊部分是⽤不到的⾮法区域，因为这个区域中的左端点⼤于右端点，不符合区间的定义；
• 每⼀个格⼦填表的时候，需要左边的格⼦以及下边的格⼦；
• 当i=j的时候，填格⼦会⽤到⾮法区域，并且i=1以及i=n的时候会越界，需要特殊处理。
  综上所述：
• 对于初始化：我们需要初始化对⻆线位置的值。因为对⻆线表⽰⻓度为1的字符串，本⾝就是回⽂串，⾥⾯的值是0即可。
• 对于填表顺序，我们有两种策略：
  a. 从下往上填写每⼀⾏，每⼀⾏从左往右。这样就能保证在填写[i,j]位置时，[i+1, j]以及[i, j-1]已经被更新过了；
  b. 第⼀维循环：⼩到⼤枚举区间⻓度len (2 <= len <= n)；第⼆维循环：枚举区间左端点i；然后计算出区间右端点j = i + len - 1。这样我们填表的时候，就是⼀个对⻆线⼀个对⻆线的填，不会产⽣越界访问的问题。
  对于区间dp的填表顺序，我们⼀般选取第⼆种，会让我们的代码看着很清晰，也⽐较符合区间的推导过程，从⼩区间递推到⼤区间

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);string s; cin >> s;int n = s.size();s = " " + s;for (int len = 2; len <= n; len++) //枚举长度for (int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;if (s[i] == s[j]) f[i][j] = f[i+1][j-1];else f[i][j] = min(f[i+1][j], f[i][j-1]) + 1;}cout << f[1][n] << endl;return 0;
}

P2858 [USACO06FEB] Treats for the Cows G/S - 洛谷

贪⼼：每次都拿两边最⼩的。反例：4, 1, 5, 3 。

• 贪⼼解：3 × 1 + 4 × 2 + 1 × 3 + 5 × 4 = 34
• 正解：4 × 1 + 1 × 2 + 3 × 3 + 5 × 4 = 35
  原因是，⿏⽬⼨光。看似当前把最⼩的拿⾛了，但是如果先拿⾛⼀个较⼤的，可能会把更⼩的暴露出来。
  正解还是⽼⽼实实的区间dp ：

1. 状态表⽰：
   dp[i][j]表⽰：把区间[i, j]的零⻝全部拿⾛，最多能得到多少钱。
2. 状态转移⽅程：
   根据先拿左边还是先拿右边，能分成两种情况讨论：
   a. 先拿左边，然后去[i + 1, j]区间获得最多的钱，即a[i] × (n - len + 1) + dp[i + 1][j] ；
   b. 先拿右边，然后去[i, j - 1]区间获得最多的钱，即a[j] × (n - len + 1) + dp[i][j - 1] ；
   因为要的是最多的钱，所以应该是上⾯两种情况的最⼤值。
3. 初始化：
   当区间⻓度为1 时：dp[i][i] = n × a[i] 。要注意，⻓度为1 ，那就是第n 次拿。
4. 填表顺序：
   先枚举区间⻓度，再枚举左端点，右端点通过计算

#include <bits/stdc++.h>
using namespace std;const int N = 2010;int n;
int a[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int len = 1; len <= n; len++)for (int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;int cnt = n - len + 1;f[i][j] = max(f[i+1][j] + a[i] * cnt, f[i][j-1] + a[j] * cnt);}cout << f[1][n] << endl;return 0;
}

P1775 石子合并（弱化版） - 洛谷

1. 状态表⽰：
   dp[i][j]表⽰：合并区间[i, j]⽯⼦，最⼩的代价。
   那么dp[1][n]就是结果
2. 状态转移⽅程：
   根据最后⼀步合并的情况，可以分成j-i种情况。设最后⼀步合并的时候，两个区间的分割点为k，也就是区间被分成[i, k]和[k + 1, j]，此时的最⼩代价为合并左边区间的最⼩代码+合并右边区间的最⼩代价+合并两个区间的代价，即
   dp[i][k] + dp[k + 1][j] + sum[i, k] + sum[k + 1, j]
   其中sum[i, k] + sum[k + 1, j]其实就是整个区间的和，可以⽤前缀和数组预处理⼀下，就可快速求出来。
   因为要的是最⼩代价，所以状态转移⽅程就是所有k 变化范围内的最⼩值。
3. 初始化：
   区间⻓度为1 的时候，不需要合并，代价为0 。
4. 填表顺序：
   先枚举区间⻓度，再枚举左端点，右端点通过计算

#include <bits/stdc++.h>
using namespace std;const int N = 310;int n;
int a[N];
int f[N][N];
int sum[N]; //前缀和数组int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];sum[i] = sum[i-1] + a[i];}//初始化memset(f, 0x3f, sizeof f);for (int i = 0; i <= n; i++) f[i][i] = 0;for (int len = 2; len <= n; len++){for (int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;int t = sum[j] - sum[i-1];//枚举分割点for (int k = i; k < j; k++){f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + t);}}}cout << f[1][n] << endl;return 0;
}

P1880 [NOI1995] 石子合并 - 洛谷

处理环形问题的技巧：倍增。
在数组后⾯，将原始数组复写⼀遍，然后在倍增之后的数组上做⼀次⽯⼦合并（弱化版），就能得到以所有位置为起点并且⻓度为len 的最⼩合并代价

#include <bits/stdc++.h>
using namespace std;const int N = 210;int n, m;
int s[N];
int f[N][N]; //最小
int g[N][N]; //最大int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++){cin >> s[i];//倍增s[i+n] = s[i];}m = n + n;//前缀和for (int i = 1; i <= m; i++){s[i] = s[i-1] + s[i];        }//初始化memset(f, 0x3f, sizeof f);memset(g, -0x3f, sizeof g);for (int i = 1; i <= m; i++){f[i][i] = g[i][i] = 0;        }for (int len = 1; len <= n; len++){for (int i = 1; i + len - 1 <= m; i++){int j = i + len - 1;int t = s[j] - s[i-1];//枚举分割点for (int k = i; k < j; k++){f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + t);g[i][j] = max(g[i][j], g[i][k] + g[k+1][j] + t);}}}int ret1 = 0x3f3f3f3f, ret2 = -0x3f3f3f3f;for (int i = 1; i <= n; i++){ret1 = min(ret1, f[i][i+n-1]);ret2 = max(ret2, g[i][i+n-1]);        }cout << ret1 << endl << ret2 << endl;return 0;
}

P3146 [USACO16OPEN] 248 G - 洛谷

1. 状态表⽰：
   dp[i][j]表⽰：将区间[i, j]合并的只剩下⼀个元素后，能得到的最⼤值。
   ⾄于为什么要定义合并剩⼀个元素，因为如果不这样定义，相邻两个区间最⼤值虽然⼀样，但是不⼀定能合并。
   那么dp 表⾥⾯的最⼤值就是结果，因为有些区间可能⽆法合并。
2. 状态转移⽅程：
   跟⽯⼦合并的讨论⽅式⼀样，根据最后⼀次合并的情况，可以把区间分成[i, k]和[k + 1, j]，要想能够合并，需要满⾜下⾯条件：
   a. 两者合并后的最⼤值⼀致，才能合并：dp[i][k] = dp[k + 1][j] ；
   b. 合并后的最⼤值不能是0 。如果是0 ，说明根本就不能合并：dp[i][k] != 0 。
   如果能合并，合并后的最⼤值就是dp[i][k] + 1。那么状态转移⽅程就是所有符合要求的k⾥⾯的最⼤值。
3. 初始化：
   所有⻓度为1的区间，合并后的最⼤值应该是⾃⼰。所以初始化所有的dp[i][i] = a[i]，也就是对⻆线。
4. 填表顺序：
   先枚举区间⻓度，再枚举左端点，右端点通过计算

#include <bits/stdc++.h>
using namespace std;const int N = 255;int n;
int a[N];
int f[N][N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;int ret = 0;for (int i = 1; i <= n; i++){cin >> a[i];f[i][i] = a[i];ret = max(ret, a[i]);}for (int len = 2; len <= n; len++){for (int i = 1; i + len - 1 <= n; i++){int j = i + len - 1;//枚举分割点for (int k = i; k <= j; k++){if (f[i][k] && f[i][k] == f[k+1][j]){f[i][j] = max(f[i][j], f[i][k] + 1);}}ret = max(ret, f[i][j]);}        }cout << ret << endl;return 0;
}