区间dp

发表于 | 更新于: | 分类于 | | 阅读数

复习一波区间dp，不然有时候玄学区间dp过题很难受，题目来源：[kuangbin带你飞]专题二十二 区间DP 。

A-Halloween Costumes

题意：有n个万圣节聚会，每个聚会有要穿一种衣服过去$a_i$，可以将一件衣服套在本来穿的衣服上，如果参加的聚会要穿的这种衣服在我外面套的衣服的里面，有两种选择，要么重新拿一件对应样式的衣服，要么脱下穿在对应样式外的所有衣服；如果里面没有对应样式的衣服，就要重新另拿一件。脱下的衣服不能重新穿回去（有些拗口，建议看题目自行体会，语文水平有限），问你对于所有聚会，所需最少的衣服数量。

思路：dp[i][j]代表区间i到j所需最少的数目，那么首先有dp[i][j]=dp[i][j-1]+1，然后在枚举断点的时候，如果枚举的断点k，有a[k]=a[j]的话，那么对于j这一点，我可以脱下dp[k+1][j-1]件衣服，回到k这一个状态点，即dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1])，注意条件不是a[i]=a[k]，因为i到k中的状态可能会影响到k到j的状态（比如说在k点，我脱下了一件后面要用到的衣服，就会有矛盾）

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int n;
int dp[maxn][maxn],a[maxn];
int main(){
    int t,cnt=1;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
            dp[i][i]=1;
        }
        for(int len=2; len<=n; len++){
            for(int i=1; i<=n; i++){
                int j=i+len-1;
                if(j>n) break;
                dp[i][j]=dp[i][j-1]+1;
                for(int k=i; k<j; k++){
                    if(a[k] == a[j]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);
                }
            }
        }
        printf("Case %d: %d\n",cnt++,dp[1][n]);
    }
}

B-Brackets

题意：一个括号序列，问你最长的匹配子序列长为多少。

思路：区间dp，转移方程：如果k和j能匹配，dp[i][j]=max(dp[i][j],dp[i][k],dp[i][k-1]+dp[k+1][j-1]+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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=110;
int dp[maxn][maxn];
char a[maxn];
bool c(char c1,char c2){
    if(c1=='(' && c2==')') return true;
    if(c1=='[' && c2==']') return true;
    return false;
}
int main(){
    while(scanf("%s",a+1)){
        if(strcmp(a+1,"end") == 0) break;
        int n=strlen(a+1);
        memset(dp,0,sizeof dp);
        for(int len=2; len<=n; len++){
            for(int i=1; i<=n; i++){
                int j=i+len-1;
                if(j>n) break;
                dp[i][j]=dp[i][j-1];
                for(int k=i; k<j; k++){
                    if(c(a[k],a[j])) dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k+1][j-1]+2);
                }
            }
        }
        printf("%d\n",dp[1][n]);
    }
}

F-You Are the One

题意：有$n$个人，每个人有一个愤怒值$a_i$，有一个小房间，根据题目意思这个小房间实现的堆栈的功能，然后对于每个人，如果他前面有$k$个人，他就会有$a_i * k$的愤怒值，小房间通过堆栈原理可以实现将位置微调，$n$个人必须依次进入小房间，问你最小的愤怒值。

思路：区间dp，而到枚举断点的时候是枚举第i个人第几个出去的，详情看代码。

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
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=110;
int dp[maxn][maxn];
char a[maxn];
int sum[maxn];
int main(){
    int t,n,cnt=1;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(dp,0,sizeof dp);
        for(int i=1; i<=n; i++){
            scanf("%d",&a[i]);
            sum[i]=sum[i-1]+a[i];
            for(int j=i+1; j<=n; j++) dp[i][j]=inf;
        }
        for(int len=2; len<=n; len++){
            for(int i=1; i<=n; i++){
                int j=i+len-1;
                if(j>n) break;
                for(int k=1; k<=len; k++){
                    dp[i][j]=min(dp[i][j],dp[i+1][k+i-1]+dp[i+k][j]+a[i]*(k-1)+(sum[j]-sum[i+k-1])*k);
                }
            }
        }
        printf("Case #%d: %d\n",cnt++,dp[1][n]);
    }
}

G-String painter

题意：两个相同长度的字符串s和t，你可以选择一段区间，将其变成同一个字符，问你将第一个字符串刷成第二串最小需要多少个操作。

思路：和A题非常相似，先用A题的思路将字符串s处理好，dp[i][j]代表区间i到j变成任意其他的字符所需的最小步数，然后再对t字符串进行处理，也是区间dp的思维，a[i]代表从1到i区间所需的最小操作。

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int dp[maxn][maxn];
char s[maxn],t[maxn];
int a[maxn];
int main(){
    while(~scanf("%s %s",s+1,t+1)){
        int n=strlen(s+1);
        for(int i=1; i<=n; i++) dp[i][i]=1;
        for(int len=2; len<=n; len++){
            for(int i=1; i<=n; i++){
                int j=i+len-1;
                if(j>n) break;
                dp[i][j]=dp[i][j-1]+1;
                for(int k=i; k<j; k++){
                    if(t[k] == t[j]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j-1]);
                }
            }
        }
        for(int i=1; i<=n; i++) a[i]=dp[1][i];
        for(int i=1; i<=n; i++){
            if(s[i] == t[i]) a[i]=a[i-1];
            else for(int j=1; j<i; j++)
                a[i]=min(a[i],a[j]+dp[j+1][i]);
        }
        printf("%d\n",a[n]);
    }
}
thanks!