链接：https://ac.nowcoder.com/acm/problem/21303
来源：牛客网
题目描述
给你一个合法的括号序列s1，每次你可以删除一个"()"
你可以删除0个或者多个"()"
求能否删成另一个括号序列s2
你可以删除0个或者多个"()"
求能否删成另一个括号序列s2
输入描述:
第一行输入一个字符串s (2 ≤ |s| ≤ 100)
第二行输入一个字符串t (2 ≤ |t| ≤ 100 ) 输出描述:
如果可以输出"Possible"
否则输出"Impossible"
示例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的时候才能进行不删除的更新
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
int n,m,i,j,k;char a[N],b[N];
int dp[N][N][N];
int main()
{
scanf("%s%s",a+,b+);
n=strlen(a+),m=strlen(b+);
dp[][][]=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
for(int k=;k<=n;k++){
if(a[i]=='('){
if(i&&k)dp[i][j][k]=max(dp[i-][j][k-],dp[i][j][k]);
if(i&&j&&a[i]==b[j]&&(!k))dp[i][j][k]=max(dp[i][j][k],dp[i-][j-][k]);
}
else{
if(i)dp[i][j][k]=max(dp[i-][j][k+],dp[i][j][k]);
if(i&&j&&a[i]==b[j]&&(!k))dp[i][j][k]=max(dp[i][j][k],dp[i-][j-][k]);
}
} }
}
if(dp[n][m][])printf("Possible\n");
else printf("Impossible\n");
return ;
}