【牛客】NC21303 删括号

给你一个合法的括号序列s1，每次你可以删除一个"()"

你可以删除0个或者多个"()"
求能否删成另一个括号序列s2

输入描述:

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

输出描述:

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

思路：dp[i][j] s串前i个字符 能否 通过删除“()”而成为 t 串的前j个字符。
归类：通过递推得到所有状态的可行性

if(s1[i] == s2[j])状态直接由前一个转移得到
　　dp[i][j] |= dp[i-1][j-1];
if(s1[i] == ')') 表示当前可以进行 删除最小长度合法括号 序列得到新的状态

但需要注意dp[i][0]时候状态的预处理
(参考牛客讨论区)
hack样例：
()(()) ——> (()) 
Ans : Possible

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <bitset>
#include <algorithm>
#include <climits>
#include<functional>
#include<time.h>
#include<stdlib.h>
#include<sstream>
#include <iomanip>
using namespace std;
#define Pair pair<int, int>
#define ULL unsigned long long
#define LS l,mid,lson
#define RS mid+1,r,rson
#define MEM(a,x) memset(a,x,sizeof(a))
#define gcd(a,b) __gcd(a,b)
#define ll long long
#define esp 1e-8
#define lowbit(x) (x&-x)
#define girlfriend zy
#define E exp(1.0)
#define PI acos(-1.0)
//#define int long long
#define pb(x) push_back(x)
#define debug(x) cout<<#x<<" "<<x<<endl;
#define rtf return false;
#define rtt return true;
void puty(){puts("YES");}
void putn(){puts("NO");}
const int maxn = 1e6 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f; ///1 061 109 567
int dp[300][300];
char s1[300];
char s2[300];
int main() {
    scanf("%s", s1+1);
    scanf("%s", s2+1);
    int n = strlen(s1+1);
    int m = strlen(s2+1);
    dp[0][0] = 1;
    for(int i=1;i<=n;i++)
    {
        if(s1[i] == ')')
        {
            int tmp = i - 1;
            int cnt2 = 1;
            while(cnt2 > 0)
            {
                if(s1[tmp] == ')')
                    cnt2++;
                else
                    cnt2--;
                tmp--;
            }
            dp[i][0] |= dp[tmp][0];
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1;j <= m ;j++)
        {
            if(s1[i] == s2[j])
                dp[i][j] |= dp[i-1][j-1];
            if(s1[i] == ')')
            {
                int tmp = i - 1;
                int cnt2 = 1;
                while(cnt2 > 0)
                {
                    if(s1[tmp] == ')')
                        cnt2++;
                    else
                        cnt2--;
                    tmp--;
                }
                dp[i][j] |= dp[tmp][j];
            }
        }
    }
    if(dp[n][m]) cout<<"Possible"<<endl;
    else cout<<"Impossible"<<endl;
}