[删括号][判断可行性的dp]

链接：https://ac.nowcoder.com/acm/problem/21303
来源：牛客网
题目描述

给你一个合法的括号序列s1，每次你可以删除一个"()"
你可以删除0个或者多个"()"
求能否删成另一个括号序列s2

输入描述:

第一行输入一个字符串s (2 ≤ |s| ≤ 100)
第二行输入一个字符串t (2 ≤ |t| ≤ 100 )

输出描述:

如果可以输出"Possible"
否则输出"Impossible"

示例1

输入

复制

(())
()

输出

复制

Possible

示例2

输入

复制

()
()

输出

复制

Possible

示例3

输入

复制

(()()())
((()))

输出

复制

Impossible

示例4

输入

复制

((())((())())())
(()(())())

输出

复制

Possible

示例5

输入

复制

((())((())())())
((()()()()()))

输出

复制

Impossible
题意：给出一个两个合法的括号序列s1,s2，对s1可以不断删除(),注意(和)要相邻，比如(()())可以删除成(())或者()或者直接删除成空串，但是不嫩删除成()()，求是否可以变成s2
题解：dp[i][j][k]表示s1位置1...i在删除掉若干个完整的()并且多删除k个(正好对应s2的1...j是否可行，由于()必须连续，所以当k>0的时候，不能不删除东西(即使s1[i]==s2[j]),也就是只有k==0的时候才能进行不删除的更新

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<set>
 6 #include<map>
 7 #include<stack>
 8 #include<vector>
 9 #include<cmath>
10 #include<algorithm>
11 using namespace std;
12 typedef long long ll;
13 const int N=105;
14 int n,m,i,j,k;char a[N],b[N];
15 int dp[N][N][N];
16 int main()
17 {
18     scanf("%s%s",a+1,b+1);
19     n=strlen(a+1),m=strlen(b+1);
20     dp[0][0][0]=1;
21     for(int i=1;i<=n;i++){
22         for(int j=0;j<=m;j++){
23             for(int k=0;k<=n;k++){
24                 if(a[i]=='('){
25                     if(i&&k)dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j][k]);
26                     if(i&&j&&a[i]==b[j]&&(!k))dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]);
27                    }
28                 else{
29                     if(i)dp[i][j][k]=max(dp[i-1][j][k+1],dp[i][j][k]);
30                     if(i&&j&&a[i]==b[j]&&(!k))dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k]);
31                 }
32             }
33 
34         }
35     }
36     if(dp[n][m][0])printf("Possible
");
37     else printf("Impossible
");
38     return 0;
39 }

View Code