mydcwfy's Blog

区间 DP

Posted on
Symbols count in article: 4.2k Reading time ≈ 9 mins.

比较灵活的一种 DP，复杂度比较高。

区间 DP

1. 分类

  1. 环形 DP 转线性 DP
  2. 记录方案数
  3. 区间 DP + 高精度
  4. 二维区间 DP

2. 例题

T1：[NOI1995] 石子合并

题目传送门 Luogu

题目传送门 AcWing

是一个模板题，大致思路是 $f[i][j]= \max(f[i][k]+f[k+1][j])+a[l]r$。

时间复杂度 $O(n^3)$。

不详细讲了。

T2：环形石子合并

题目传送门 AcWing

和上一题其实没有大区别，只是可以首尾合并。

现在怎么办呢？

首先，我们可以发现，合并完后，一定会有相邻的两个点是没有合并的。

于是，我们可以枚举相邻的两个点，从中间断开，就可以转换成链了。

但是，这个的复杂度为 $O(n\times n^3=n^4)$，会超时。

怎么优化呢？

我们将整个的环断开，复制一倍在末尾。

按链来计算，我们再枚举起点，$f[i][i+n-1]$ 即为答案。

T3：[NOIP2006] 能量项链

题目传送门 Luogu

题目传送门 AcWing

可能很多同学都会想到贪心，但是是有问题的。

其实还是一个区间 DP，和上一题没有大区别。

考虑边界问题，有一些不同。

$f[i][j]=\max(f[i][k]+f[k][j]+a[i]a[k]a[j])i<k<j$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=205;
int a[N],f[N][N],n;

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",a+i);
    for (int i=1;i<=n;++i) a[i+n]=a[i];
    for (int len=1;len<=2*n;++len)
        for (int i=1;i<=2*n-len+1;i++)
        {
            int j=i+len-1;
            if (len==1)
            {
                f[i][j]=0;
                continue;
            }
            for (int k=i+1;k<j;++k)
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
        }
    int res=0;
    for (int i=1;i<=n;++i) res=max(res,f[i][i+n]);
    printf("%d\n",res);
    return 0;
}

T4：凸多边形的划分

题目传送门 LOJ

看似无从下手。

现在，我们先考虑对于一条边，我们必须找到一个点来使这条边构成一个三角形。

枚举这个点，我们发现可以将整个图转化为三个部分，于是就划分为了三个子问题。

于是，我们就可以区间 DP 了！

具体来说，我们选取 $[L,R]$ 这条边，然后枚举对应的点，然后划分为 $[L,i],[i,R],(L,i,R)$ 三部分。

最后要注意的是，答案很大，需要使用该精度。

T5：[NOIP2003] 加分二叉树

题目传送门 AcWing

题目传送门 Luogu

题目本身不难，但是我们要学习区间 DP 的思想。

我们发现，在中序遍历中，左子树一定会根节点的左边，右子树一定在根节点的右边。

于是，我们可以枚举当前的根节点，然后就可以划分为几个了。

$f[i,j]=\max(f[i][k-1]\times f[k+1][j]+a[k])(i<k<j)$。

同时，我们要记录答案的来源。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=35;
ll f[N][N];
int n,g[N][N],a[N];

void print(int l,int r)
{
    if (l>r) return;
    printf("%d ",g[l][r]);
    if (l==r) return;
    if (l!=g[l][r]) print(l,g[l][r]-1);
    if (r!=g[l][r]) print(g[l][r]+1,r);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    for (int len=1;len<=n;++len)
        for (int l=1;l<=n-len+1;++l)
        {
            int r=l+len-1;
            ll &val=f[l][r];
            if (l==r)
            {
                val=a[l];
                g[l][r]=l;
                continue;
            }
            if (f[l+1][r]+a[l]>=f[l][r-1]+a[r])
            {
                val=f[l+1][r]+a[l];
                g[l][r]=l;
            }
            else{
                val=f[l][r-1]+a[r];
                g[l][r]=r;
            }
            for (int k=l+1;k<r;++k)
            {
                if (val<f[l][k-1]*f[k+1][r]+a[k])
                {
                    val=f[l][k-1]*f[k+1][r]+a[k];
                    g[l][r]=k;
                }
            }
        }
    printf("%lld\n",f[1][n]);
    print(1,n);
    return 0;
}

T6：[NOI1999] 棋盘分割

题目传送门 Luogu

题目传送门 AcWing

首先一阵推导：

于是，我们就是要使 $\sum_{i=1}^nx_i^2$ 最小。

首先，分为横切和纵切。

然后，我们还要看是哪一边继续切割，就递归统计答案。

对于另一边，我们可以使用二维前缀和快速计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define sqr(x) (x*x)
using namespace std;

const int N=20,M=9,INF=0x3f3f3f3f; 

int n=8,k;
int s[M][M];
double f[M][M][M][M][N],X;

inline double get_matrix(int xa,int ya,int xb,int yb)
{
    double t=(double)s[xb][yb]-s[xa-1][yb]-s[xb][ya-1]+s[xa-1][ya-1]-X;
    return t*t/k;
}

double dp(int xa,int ya,int xb,int yb,int k)
{
    double &v=f[xa][ya][xb][yb][k];
    if (v>=0) return v;
    if (k==1) return v=(get_matrix(xa,ya,xb,yb));
    v=1e9;
    for (int i=xa;i<xb;++i)
    {
        v=min(v,(get_matrix(xa,ya,i,yb))+dp(i+1,ya,xb,yb,k-1));
        v=min(v,(get_matrix(i+1,ya,xb,yb))+dp(xa,ya,i,yb,k-1));
    }
    for (int i=ya;i<yb;++i)
    {
        v=min(v,(get_matrix(xa,ya,xb,i))+dp(xa,i+1,xb,yb,k-1));
        v=min(v,(get_matrix(xa,i+1,xb,yb))+dp(xa,ya,xb,i,k-1));
    }
    // printf("%d %d %d %d %d:%d\n",xa,ya,xb,yb,k,v);
    return v;
}

int main()
{
    scanf("%d",&k);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
        {
            scanf("%d",&s[i][j]);
            s[i][j]-=s[i-1][j-1]-s[i][j-1]-s[i-1][j];
        }
    X=(double)s[n][n]/k;
    memset(f,-1,sizeof f);
    // printf("%.3lf\n",(double)dp(1,1,n,n,k));
    printf("%.3lf\n",sqrt(dp(1,1,n,n,k)));
    return 0;
}