总目录

在线测评地址(ybt)

在线测评地址(LOJ)

1.题意不明40分

ybt

未通过

测试点	结果	内存	时间
测试点1	答案错误	604KB	2MS
测试点2	答案错误	608KB	4MS
测试点3	答案错误	608KB	2MS
测试点4	答案正确	612KB	1MS
测试点5	答案正确	612KB	1MS

LOJ

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

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

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

可能遇到的情况

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

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

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

#include <bits/stdc++.h>
#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<n;i++)
		if(s[i]=='(')lt1++;
		else if(s[i]==')'){
			if(lt1==0)rt1++;
			else lt1--;
		}else if(s[i]=='[')lt2++;
		else if(s[i]==']'){
			if(lt2==0)rt2++;
			else lt2--;
		}
	printf("%d\n",lt1+rt1+lt2+rt2);
	return 0;
}

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 <bits/stdc++.h>
#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;len<n;len++)
		for(lt=1;lt<=n;lt++){
			rt=lt+len;
			if(rt>n)break;
			if((s[lt]=='('&&s[rt]==')')||(s[lt]=='['&&s[rt]==']'))
				dp[lt][rt]=dp[lt+1][rt-1]+2;
			for(k=0;k<len;k++){
				dp[lt][rt]=max(dp[lt][rt],dp[lt][lt+k]+dp[lt+k+1][rt]);
			}
		}
	printf("%d\n",n-dp[1][n]);
	return 0;
} 

通过该题习得什么？

逆向思维，好难想啊。

两个转移方程，更难想了。