|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
区间 DP 套路是设定 [l, r] 区间的答案, 然后枚举中间点转移
当然也就是考虑子问题如何拼成原来的问题
想出正解也要考虑这样子的解法有没有必要, 有没有更简单的做法
注意如果状态不足够描述应该考虑增加状态 / 让状态更加细分
下面是做的几道题
栗子1 - 区间回文串
本题相当于二维前缀和, 并不是传统的枚举中间点, 而是直接从小到大转移
- #include <bits/stdc++.h>
- using namespace std;
- const int P = 1e9 + 7;
- const int B = 131;
- const int N = 5005;
- string s;
- int n, Q;
- int f[N][N];
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> s;
- n = s.size();
- s = '-' + s;
- for (int cen = 1; cen <= n; cen++) {
- for (int l = cen, r = cen; l >= 1 && r <= n && s[l] == s[r]; l--, r++) {
- f[l][r]++;
- }
- for (int l = cen, r = cen + 1; l >= 1 && r <= n && s[l] == s[r]; l--, r++) {
- f[l][r]++;
- }
- }
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- f[i][j] += f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1];
- // cout << f[i][j] << ' ';
- }
- // cout << '\n';
- }
- cin >> Q;
- while (Q--) {
- int l, r;
- cin >> l >> r;
- cout << f[r][r] - f[l - 1][r] - f[r][l - 1] + f[l - 1][l - 1] << '\n';
- }
- return 0;
- }
复制代码
括号序列类区间 DP
栗子2 - 括号构造
给出一些由"(",")","[","]"构成的序列,请添加尽量少的括号,得到一个合法序列, 输出补起来之后的序列
我们可以首先 dp 求解每个区间里需要添加的最少的括号, 然后递归输出 (每次拨开区间两端点, 如果 dp 值无变化, 说明这个括号序列已经配对, 递归输出后面的
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 105;
- string s;
- map<char, char> dict;
- int f[N][N], n;
- void dfs(int l, int r) {
- if (r < l)
- return;
- // 需要配对的肯定只剩下一边
- if (r == l) {
- if (s[l] == '(' || s[l] == ')')
- cout << "()";
- else
- cout << "[]";
- return;
- }
- // 如果外围正常
- if (s[r] == dict[s[l]] && f[l][r] == f[l + 1][r - 1]) {
- cout << s[l];
- dfs(l + 1, r - 1);
- cout << s[r];
- return;
- }
- // 看看是哪个点转移到当前区间答案, 破开来输出
- for (int i = l; i <= r - 1; i++) {
- if (f[l][i] + f[i + 1][r] == f[l][r]) {
- dfs(l, i);
- dfs(i + 1, r);
- return;
- }
- }
- }
- int main() {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> s;
- n = s.size();
- s = 'A' + s;
- dict['('] = ')';
- dict['['] = ']';
- for (int i = n; i >= 1; i--) {
- f[i][i] = 1;
- for (int j = i + 1; j <= n; j++) {
- f[i][j] = 1e9;
- // 如果配对, 就是子区间的答案
- if (s[j] == dict[s[i]])
- f[i][j] = min(f[i][j], f[i + 1][j - 1]);
- // 枚举中间点转移
- for (int k = i; k <= j - 1; k++) {
- f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
- }
- }
- }
- dfs(1, n);
- return 0;
- }
复制代码
栗子3 - P7914 [CSP-S 2021] 括号序列
这题真难qwq
如何给状态集合分类?
很容易想到以 (-*, (-), *-), *-* 四种区间两端的特征来划分
但是这样会重复计算, 例如 ()()() 这个序列会被子问题计算两次
这里我们就需要细分状态, 保证转移单一, 怎么想到的呢 ? 不知道, 但是记住就行了吧
不过应该是有迹可循的, 我们每次想让最左边的序列更新大的序列, 就想到配对的括号和不配对的括号吧
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N = 505;
- const ll P = 1e9 + 7;
- int n, k;
- ll f[N][N][5];
- string s;
- bool Ispair(int x, int y){
- return ((s[x] == '(' || s[x] == '?') && (s[y] == ')' || s[y] == '?'));
- }
- void Init(){
- s = '-' + s;
- for(int i = 1; i <= n; i++){
- if(i < n && Ispair(i, i + 1)){
- f[i][i + 1][1] = f[i][i + 1][0] = 1;
- }
- for(int j = i; j <= n; j++){
- if((s[j] != '*' && s[j] != '?') || j - i + 1 > k) break;
- f[i][j][4] = 1;
- }
- }
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
-
- cin >> n >> k >> s;
- Init();
- for(int len = 3; len <= n; len++){
- for(int i = 1; i + len - 1 <= n; i++){
- int j = i + len - 1;
- // 0 (...) 外层匹配
- // 1 (...)(...) 最外层是括号
- // 2 (...)** AS
- // 3 **(...) SA
- // 4 ******* 全*
- // 1 包含 0 的情况
- // (...) 0 = 1 + 2 + 3 + 4 (i+1, j-1)
- // AB 1 = 0 * 1 枚举断点
- // ASB 1 = 0 * 3 枚举断点
- // SA 3 = 4 * 1
- // AS 2 = 1 * 4
-
- // (...) 外层匹配
- if(Ispair(i, j)){
- 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];
- f[i][j][0] %= P;
- }
- // AB, ASB
- for(int cut = i; cut < j; cut++){
- f[i][j][1] += f[i][cut][0] * (f[cut + 1][j][1] + f[cut + 1][j][3]) % P;
- f[i][j][1] %= P;
- }
- for(int cut = i; cut < j; cut++){
- f[i][j][3] += f[i][cut][4] * f[cut + 1][j][1];
- f[i][j][3] %= P;
- }
-
- for(int cut = j; cut > i; cut--){
- f[i][j][2] += f[i][cut - 1][1] * f[cut][j][4];
- f[i][j][2] %= P;
- }
- f[i][j][1] += f[i][j][0];
- f[i][j][1] %= P;
- }
- }
- cout << f[1][n][1];
-
- return 0;
- }
复制代码
栗子4 - P10622 [ICPC2013 WF] Matryoshka
这题自己做的时候是按照 1 的地方划分区间, 然后做一个简单的 "只有一组套娃" 的区间 dp, 然鹅不知道什么原因一直错几个点
后来看题解发现不需要, 只需要看区间里没有相同数即可 (额但是题目说是 1-m, 所以我的更严谨吧...)
总的来说想出解法之后看看是否有必要这么复杂, 要抓住根本
- #include <bits/stdc++.h>
- using namespace std;
- const int N = 505;
- const int M = 0x3f3f3f3f;
- int n;
- int sum[N][N], minv[N][N], maxv[N][N], maxpos[N][N];
- int temp[N], l1[N], arr[N];
- int pos[N], top;
- int f[N][N], g[N];
- // f[l, r] 表示 [l, r] 区间拼套娃组的最小花费
- // g[p] 表示前 p 个套娃已经装好的最小花费
- void Init(){
- memset(g, 0x3f, sizeof(g));
- memset(f, 0x3f, sizeof(f));
- g[0] = 0;
- for(int i = 1; i <= n + 1; i++){
- f[i][i] = 0;
- minv[i][i] = arr[i];
- maxv[i][i] = arr[i];
- maxpos[i][i] = temp[i];
- for(int j = i + 1; j <= n; j++){
- minv[i][j] = min(minv[i][j - 1], arr[j]);
- maxv[i][j] = max(maxv[i][j - 1], arr[j]);
- maxpos[i][j] = max(maxpos[i][j], temp[j]);
- }
- for(int j = 1; j < N; j++){
- sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
- }
- }
- }
- int getsum(int a, int b, int c, int d){
- return (sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1]);
- }
- int cost(int i, int k, int j){
- return (getsum(i, minv[k + 1][j], k, N - 1) + getsum(k + 1, minv[i][k], j, N - 1));
- }
- int main(){
- ios::sync_with_stdio(0);
- cin.tie(0);
- cin >> n;
- for(int i = 1; i <= n; i++){
- int x;
- cin >> x;
- sum[i][x]++;
- arr[i] = x;
- temp[i] = l1[x];
- l1[x] = i;
- }
- Init();
- for(int len = 1; len <= n; len++){
- for(int i = 1; i + len - 1 <= n; i++){
- int j = i + len - 1;
- if(maxpos[i][j] >= i) continue;
- for(int k = i; k < j; k++){
- f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + cost(i, k, j));
- }
- }
- }
- for(int i = 1; i <= n; i++){
- for(int j = 1; j <= i; j++){
- // 符合条件的才能接上去
- if(maxpos[j][i] < j && minv[j][i] == 1 && maxv[j][i] == i - j + 1){
- g[i] = min(g[i], g[j - 1] + f[j][i]);
- }
- }
- }
- if(g[n] != M) cout << g[n];
- else cout << "Impossible";
- return 0;
- }
复制代码
|
评分
-
查看全部评分
|