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

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

总目录

在线测评地址(ybt)

在线测评地址(LOJ)

1.题意不明40分

ybt

未通过

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

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答案正确700KB4MS测试点2答案正确696KB2MS测试点3答案正确708KB2MS测试点4答案正确676KB2MS测试点5答案正确636KB2MS
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 
通过该题习得什么？
 
逆向思维，好难想啊。
 
两个转移方程，更难想了。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5702605.html