链接:https://ac.nowcoder.com/acm/problem/21303?&headNav=acm 来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 524288K,其他语言1048576K 64bit IO Format: %lld
给你一个合法的括号序列s1,每次你可以删除一个"()" 你可以删除0个或者多个"()" 求能否删成另一个括号序列s2
示例1
复制
(()) ()复制
Possible示例2
复制
() ()复制
Possible示例3
复制
(()()()) ((()))复制
Impossible示例4
复制
((())((())())()) (()(())())复制
Possible示例5
复制
((())((())())()) ((()()()()()))复制
Impossible
先观察这道题.题目所说的可删的括号必须相邻且"可动态",即((()()))在删()()后,可继续删(),再删().
如果一对()一对()dp的话,记录每一对的位置及存在性会很麻烦,或许要2^50的复杂度,很明显不行
不如用k = 删掉的'('数 - 删掉的')'数,当k = 0时,操作可行(因为有重要前提s1合法)
想到这里思路就应该很清晰了:
设dp[i][j][k]表示s1[i]和s2[j]位置 在k = 删掉的'('数 - 删掉的')'数时可否匹配(相当于bool类型) 若k==0,则可匹配s2中的下一个括号 否则,继续遍历s1,直到k = 0才能进行上一步 最后答案就是dp[len1][len2][0]是否可行 复杂度O(N^3) --------------------- 作者:VibrantY 来源: 原文:https://blog.csdn.net/weixin_42483016/article/details/90709357 版权声明:本文为博主原创文章,转载请附上博文链接!
菜鸡只想到了模拟~~~
那个“合法”二字很重要,读题的时候并没注意
#include<bits/stdc++.h> using namespace std; typedef long long ll; char a[105],b[105]; bool dp[105][105][55]; int main(){ scanf("%s%s",a+1,b+1); int la=strlen(a+1); int lb=strlen(b+1); dp[0][0][0]=1; for(int i=0;i<la;i++){ for(int j=0;j<lb;j++){ for(int k=0;k<la/2;k++){ if(dp[i][j][k]){ if(k==0&&a[i+1]==b[j+1]) dp[i+1][j+1][0]=true; if(a[i+1]=='(') dp[i+1][j][k+1]=true; else if(k) dp[i+1][j][k-1]=true; } } } } if(dp[la][lb][0]) printf("Possible\n"); else printf("Impossible\n"); return 0; }