To boldly go where no one has gone before.

【学习笔记】区间dp

2019-05-29 22:54:53


例题 P1880

分析

一堆石子在环上,需要合并成一堆,合并时得到的分数为合并后石子的重量,求得到的最大/最小分数。

这很明显就是个区间$\text{dp}$,只是相对来说如何进行状态转移比较蛋疼。

转移方程

用$f[i][j]$表示将$[i,j]$区间内的石子合并之后得到的最大分数,那么就可以枚举断点$k\in[i,j)$,进行状态转移:$$f[i][j]=\max\ f[i][k]+f[k+1][j]+sum(i,j)$$ 然后就可以很明显地注意到,虽然转移方程好写,但是以什么样的顺序来进行转移就比较蛋疼了。如果单纯地枚举$i,j$,然后枚举$k$,那么很可能$f[i][k]$和$f[k+1][j]$是根本还没有计算的状态,那么就没有转移的意义了。

所以换个思想,我们希望的是从简单到复杂地考虑,比如第一次转移肯定希望是最开始的两堆石子合并,然后第二次转移就是第一次合并之后的石子和相邻石子合并$\cdots$以此类推。这样一想,很明显地发现我们需要的是$d=(j-i)$这个式子递增,也就是应该先枚举$d$,然后枚举$i$,最后根据定义,$j=i+d$,就可以保证每次转移的$f[i][k]$和$f[k+1][j]$都是已经计算过的状态。


总结

这里强调的就是:枚举顺序非常重要!可以按照这个思路考虑:

  1. 能否覆盖全状态?
  2. 用于转移的状态是否已经确定?
  3. 是否修改了已经计算好的状态?

Add

2019-7-11复习了一次区间$\text{dp}$,然后我觉得我的理解更加深刻了。

首先,既然是区间$\text{dp}$,一定要找的就是区间。$f[i][j]$描述的是$\left[ i,j\right]$区间,还是两个序列的$[1,i]$和$[1,j]$的对应关系?初始的区间有哪些,它们的值分别是多少?

其次,以什么样的顺序枚举?如果是类似分治的思想,需要用小区间合并得到大区间,那么一定是从$len$开始枚举。否则,两层枚举顺序就没有限制。

最后,怎么样合并信息?有没有额外的变动?最后获得的答案在哪一个区间?


P2758

这道题说的是给出替换、插入、删除三种操作,将字符串A变为字符串B,询问需要进行的最少操作次数。(A,B字符串长度不一定相等)

想不到吧! 这是个区间$\text{dp}$呢!

考虑之后,我建立的模型是$f[i][j]$表示用A串的$[1,i]$区间变为B串的$[1,j]$区间所需要的最少操作次数。

  1. 不需要进行操作,直接赋值。
  2. 插入,$f[i][j]=f[i][j-1]+1$。
  3. 删除,$f[i][j]=f[i-1][j]+1$。
  4. 替换,$f[i][j]=f[i-1][j-1]+1$。

最后,对于上述四种情况取最小值即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2010;
char s1[MAXN], s2[MAXN];
int f[MAXN][MAXN], len1, len2;

int main()
{
    scanf("%s", s1);
    len1 = strlen(s1);
    getchar();
    scanf("%s", s2);
    len2 = strlen(s2);
    for(int i = 1; i <= len1; i++)
        f[i][0] = i; //全部删除
    for(int i = 1; i <= len2; i++)
        f[0][i] = i; //全部插入
    for(int i = 1; i <= len1; i++)
        for(int j = 1; j <= len2; j++)
        {
            if(s1[i - 1] == s2[j - 1])
                f[i][j] = f[i - 1][j - 1];
            else
                f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
        }
    printf("%d", f[len1][len2]);
    return 0;
}

POJ 2955

找出最长的匹配括号子序列,想不到吧! 这又是个区间$\text{dp}$!

假设有一个待考虑的区间$[i,j]$,获得它的匹配括号子序列有两种办法:

  1. 利用 a => (a) 首尾匹配,那么$f[i][j]=f[i+1][j-1]+1$。
  2. 利用 a, b => ab 把它从中间砍断,前后分别考虑,那么$f[i][j]=f[i][k]+f[k+1][j]$。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 110;
char s[MAXN];
int T, n, f[MAXN][MAXN];

bool match(char a, char b)
{
    return (a == '(' && b == ')') || (a == '[' && b == ']');
}

int main()
{
    while(1)
    {
        memset(f, 0, sizeof(f));
        scanf("%s", s);
        getchar();
        if(s[0] == 'e')
            return 0;
        n = strlen(s);
        for(int len = 2; len <= n; len++)
            for(int i = 0, j = i + len - 1; j < n; i++, j++)
            {
                if(match(s[i], s[j]))
                    f[i][j] = f[i + 1][j - 1] + 2;
                for(int k = i; k < j; k++) //得充分考虑!!
                    f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j]);
            }
        printf("%d\n", f[0][n - 1]);
    }
    return 0;
}

POJ 1651

给定一个序列,要从中一直拿数直到只剩两个数,每次拿出去的时候获得一个分数,分数等于拿走的数与它相邻两数之积。使获得分数最小。

实际上这道题难在建模。用$f[i][j]$表示$[i,j]$区间拿到只剩首尾两数获得的最小分数,考虑一个区间$[i,j]$,如果我把这个区间拿到只剩$a[i],a[k],a[j]\ (i<k<j)$三个数,再把$a[k]$拿掉,获得的分数就很显然了。那么拿到只剩三数这个过程就可以继续分治,最后很轻松就获得了答案。

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
using namespace std;
const int MAXN = 110;
// f[i][j] = min(f[i][k] + f[k][j] + a[k] * a[i] * a[j])
int n, a[MAXN];
int f[MAXN][MAXN];

int main()
{
    memset(f, 0x3f, sizeof(f));
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++)
        f[i][i] = 0;
    for(int i = 1; i < n; i++)
        f[i][i + 1] = 0;
    for(int len = 3; len <= n; len++)
        for(int i = 1, j = i + len - 1; j <= n; i++, j++)
            for(int k = i + 1; k < j; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[k] * a[j]);
    printf("%d", f[1][n]);
    return 0;
}

LightOJ 1422

有一些衣服,可以套着穿,但是脱了就报废,求最少要多少件衣服才够穿。

这题简单粗暴,只要发现一个区间首尾需要穿的衣服一样,那就可以套在里面穿其他衣服。剩余的常规操作即可。这道题难在如何用莽夫思维简化问题。

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN = 110;
int n, c[MAXN];
int f[MAXN][MAXN]; 

int main()
{
    int T, cas = 0;
    scanf("%d", &T);
    while(T--)
    {
        cas++;
        memset(f, 0x3f, sizeof(f));
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &c[i]);
        for(int i = 1; i <= n; i++)
            f[i][i] = 1;
        for(int len = 2; len <= n; len++)
            for(int i = 1, j = i + len - 1; j <= n; i++, j++)
            {
                if(c[i] == c[j])
                    f[i][j] = f[i][j - 1];
                for(int k = i; k < j; k++)
                    if(c[i] == c[k])
                        f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);
            }
        printf("Case %d: %d\n", cas, f[1][n]);
    }   
    return 0;
}