NC21303. 删括号

描述

输入描述

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

输出描述

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

示例1

输入:

(())
()

输出:

Possible

示例2

输入:

()
()

输出:

Possible

示例3

输入:

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

输出:

Impossible

示例4

输入:

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

输出:

Possible

示例5

输入:

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

输出:

Impossible

原站题解

#include<cstdio>
#include<cstring>
const int N=105;
int n,m,i,j,k;char a[N],b[N];bool f[N][N][N];
int main(){
  scanf("%s%s",a+1,b+1);
  n=strlen(a+1),m=strlen(b+1);
  f[0][0][0]=1;
  for(i=0;i<n;i++)for(j=0;j<=m;j++)for(k=0;k<=n;k++)if(f[i][j][k]){
    if(!k&&a[i+1]==b[j+1])f[i+1][j+1][k]=1;
    if(a[i+1]=='(')f[i+1][j][k+1]=1;
    else if(k)f[i+1][j][k-1]=1;
  }
  puts(f[n][m][0]?"Possible":"Impossible");
}