一个动态规划！旁边说了Special Judge，等于说正确结果是不唯一的。
就拿测试数据来说吧：
Sample Input

([(]
Sample Output

()[()]

这确实是正确答案，但似乎([()])应该也是正确答案啊！！！

		for(i=1;i<len;i++) dp[i][i-1]=0;
		for(i=0;i<len;i++) dp[i][i]=1;
		for(s=1;s<len;s++)
			for(i=0;i<len-s;i++)
			{
				j=i+s;
				sum=INT_MAX;
				if(str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']')
				{sum=dp[i+1][j-1];track[i][j]=-1;}
				if(str[i]=='('||str[i]=='[')
				{
					if(dp[i+1][j]+1<sum)
					{sum=dp[i+1][j]+1;track[i][j]=-2;}
				}
				if(str[i]==')'||str[i]==']')
				{
					if(dp[i][j-1]+1<sum)
					{sum=dp[i][j-1]+1;track[i][j]=-3;}
				}
				for(k=i;k<j;k++)
				{
					temp=dp[i][k]+dp[k+1][j];
					if(temp<sum) 
					{
						sum=temp;
						track[i][j]=k;
					}
				}
				dp[i][j]=sum;
			}

这样的dp应该是正确的！逻辑上时正确的。
改成了：
		for(i=1;i<len;i++) dp[i][i-1]=0;
		for(i=0;i<len;i++) dp[i][i]=1;
		for(s=1;s<len;s++)
			for(i=0;i<len-s;i++)
			{
				j=i+s;
				sum=INT_MAX;
				if(str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']')
				{sum=dp[i+1][j-1];track[i][j]=-1;}
				/*if(str[i]=='('||str[i]=='[')
				{
					if(dp[i+1][j]+1<sum)
					{sum=dp[i+1][j]+1;track[i][j]=-2;}
				}
				if(str[i]==')'||str[i]==']')
				{
					if(dp[i][j-1]+1<sum)
					{sum=dp[i][j-1]+1;track[i][j]=-3;}
				}*/
				for(k=i;k<j;k++)
				{
					temp=dp[i][k]+dp[k+1][j];
					if(temp<sum) 
					{
						sum=temp;
						track[i][j]=k;
					}
				}
				dp[i][j]=sum;
			}
却AC了。
明显上一种较这种更有前途对啊！！！
仔细看了看题：
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
最后一句话([()])也是满足的。


奇怪的AC!!!
 
希望以后知道为什么！~

• Re:奇怪这道题？？？不服这样的AC (51) liql2008 2009-05-12 14:33:56
• 不奇怪吧?~~ (221) userfriendly 2009-05-26 17:10:07