删括号

思路

图片说明

代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

bool f[111][111][111];
char s[111],t[111];
int main(){
    scanf("%s %s",s+1,t+1);
    f[0][0][0] = true;
    int lens = strlen(s+1),lent = strlen(t+1);
    for(int i = 0;i<lens;i++){
        for(int j = 0;j<lent;j++){
            for(int k = 0;k<=lens/2;k++){
                if(f[i][j][k]){
                    char c1 = s[i+1],c2 = t[j+1];
                    if(c1 == '(' && c2 == '(') {
                        if(!k) f[i+1][j+1][k] = true;
                        f[i+1][j][k+1] = true;
                    }
                    if(c1 == ')' && c2 == ')') {
                        if(!k) f[i+1][j+1][k] = true;
                        if(k)  f[i+1][j][k-1] = true;
                    }
                    if(c1 == '(' && c2 == ')') f[i+1][j][k+1] = true;
                    if(c1 == ')' && c2 == '(' && k) f[i+1][j][k-1] = true;
                }
            }
        }
    }
    if(f[lens][lent][0]) puts("Possible");
    else puts("Impossible");
    return 0;
}