1572 括号配对(LOJ10150) 题意不明40分 括号配对 逆向思维 两个转移方程 区间动归100分

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

1.题意不明40分

ybt

未通过

LOJ

题目难懂，关键还是样例太少，难道只是简单配对？

题中可能出现的字符是哪些？

按栈的方式来配对，试试。

可能遇到的情况

)))(((]]][[[

个人认为，需要增加的最少字符数是12.先按这个编.

样例通过，上述例子通过，提交40分。代码如下：

#include 
#define maxn 110
using namespace std;
char s[maxn];
int main(){
	int n,i,lt1,rt1,lt2,rt2;
	scanf("%s",s);
	n=strlen(s);
	lt1=rt1=lt2=rt2=0;
	for(i=0;i 
2.括号配对 逆向思维 两个转移方程 区间动归100分
 
ybt
 
通过
 
测试点
结果
内存
时间
测试点1
答案正确
700KB
4MS
测试点2
答案正确
696KB
2MS
测试点3
答案正确
708KB
2MS
测试点4
答案正确
676KB
2MS
测试点5
答案正确
636KB
2MS
LOJ
 
 
翻看他人思路，发现上述思路基本正确，主要是考虑不周，如下例子
 
输入：
([)]
输出：
2
 
继续翻看，发现，这一点就是一个很大的境界：
 
需要补上的括号数=没有成功配对的括号数=总括号数-能正确配对的括号数。
 
逆向思维啊，这就难倒一大片。
 
继续思路(发现离想到，还差很远)：
 
转移方程有两个.好难想啊
 
用f[i][j]表示i到j区间内能配对成功的括号数。
 
　　那么f[i][j]怎么转移呢？如果用s数组来表示字符串，那么如果s[i]==s[j](即(s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))，那么就有f[i][j]=f[i+1][j-1]+2。可能有点难理解，图解一下：
 
 
那么这是s[i]==s[j]时的操作（难点），剩下的就是老套路了，f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]).
 
输入：
([)]
输出：
2
 
 
 针对上述例子，遍历区间如下：
 
lt=1 rt=2 1 1 2 2
lt=2 rt=3 2 2 3 3
lt=3 rt=4 3 3 4 4
lt=1 rt=3 1 1 2 3
lt=1 rt=3 1 2 3 3
lt=2 rt=4 2 2 3 4
lt=2 rt=4 2 3 4 4
lt=1 rt=4 1 1 2 4
lt=1 rt=4 1 2 3 4
lt=1 rt=4 1 3 4 4
2
 
对应的dp[lt][rt]值如下：
 
位置1234
字串([)]

([   dp[1][2]=0
[)   dp[2][3]=0
)]   dp[3][4]=0
([)  dp[1][3]=2
[(]  dp[2][4]=2
([)] dp[1][4]=2
2
 
括号配对 逆向思维 两个转移方程 区间动归100分 代码如下：
 
#include 
#define maxn 110
using namespace std;
char s[maxn];
int dp[maxn][maxn];
int main(){
	int n,len,lt,rt,k;
	scanf("%s",s+1);
	n=strlen(s+1);
	for(len=1;lenn)break;
			if((s[lt]=='('&&s[rt]==')')||(s[lt]=='['&&s[rt]==']'))
				dp[lt][rt]=dp[lt+1][rt-1]+2;
			for(k=0;k 
通过该题习得什么？
 
逆向思维，好难想啊。
 
两个转移方程，更难想了。