题解 | #删括号#

思路借鉴楼下Joseph1314, 发现其中有些问题更正一下：

代码的初始化有些许问题，f[k][0]即s串有k位, t串没有字符时，是由可能为true的，但是其代码没有对这一部分进行初始化。详情见代码即注释。

// Problem: 删括号
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/21303
// Memory Limit: 2 MB
// Time Limit: 21303000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>


using namespace std;
typedef long long LL;
const int N = 110;

char s[N], t[N];
bool f[N][N];


void f_init()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

}

int main()
{
	f_init();
	cin >> s + 1 >> t + 1;
	
	int slen = strlen(s + 1), tlen = strlen(t + 1);
	
	
	t[0] = '@'; //t 为空串时，s[k] (k != 0) 不可能相等。故初始化为‘@’；
	f[0][0] = true;
	 
	for(int i = 1; i <= slen; i ++)
	for(int j = 0; j <= tlen; j ++) // 循环从0开始，这样可以初始化其中f[k][0] 为true的部分
	{
		if(s[i] == t[j]) f[i][j] |= f[i - 1][j - 1];
		if(s[i] == ')')
		{
			int k = i - 1;
			int cnt = 1;
			while(k > 0 && cnt > 0)
			{
				if(s[k] == ')')cnt ++;
				else cnt --;
				k --;
			}
			f[i][j] |= f[k][j];
		}
	}
	
	if(f[slen][tlen]) cout << "Possible" << endl;
	else cout << "Impossible" << endl;
}