| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
wa了好几次 假设你的dp正确 wa的原因是要么没有注意空行的输入 要么是保存最终答案的字符串数组开得太小//我的程序是一边dp一边生成答案 没有用递归去输出答案 那我不太会
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[101][101];
char s[101],ans[101][101][201];
bool check(char c1,char c2)
{
return((c1=='[' && c2==']')||(c1=='(' && c2==')'));
}
int main()
{
int i,j,k,l,n;
gets(s);
if(strlen(s))
{
if(s[strlen(s)-1]==' ')
{
cout<<endl;
return 0;
}
n=strlen(s)-1;
for(i=0;i<=n;i++)
{
for(j=0;j<=n;j++) dp[i][j]=100000;
}
for(i=0;i<n;i++)
{
if(!check(s[i],s[i+1]))
{
dp[i][i+1]=2;
if(s[i]=='[' || s[i]==']') ans[i][i+1][0]='[',ans[i][i+1][1]=']';
else ans[i][i+1][0]='(',ans[i][i+1][1]=')';
if(s[i+1]=='[' || s[i+1]==']') ans[i][i+1][2]='[',ans[i][i+1][3]=']';
else ans[i][i+1][2]='(',ans[i][i+1][3]=')';
ans[i][i+1][4]='\0';
}
else dp[i][i+1]=0,ans[i][i+1][0]=s[i],ans[i][i+1][1]=s[i+1],ans[i][i+1][2]='\0';
dp[i][i]=1;
if(s[i]=='[' || s[i]==']') ans[i][i][0]='[',ans[i][i][1]=']';
else ans[i][i][0]='(',ans[i][i][1]=')';
ans[i][i][2]='\0';
};
dp[n][n]=1;
if(s[n]=='[' || s[n]==']') ans[n][n][0]='[',ans[n][n][1]=']';
else ans[n][n][0]='(',ans[n][n][1]=')';
ans[i][i][2]='\0';
for(l=3;l<=n+1;l++)
for(i=0;i<=n-l+1;i++)
{
j=i+l-1;
ans[i][j][0]='\0';
if(check(s[i],s[j]))
{
dp[i][j]=dp[i+1][j-1];
ans[i][j][0]=s[i];
ans[i][j][1]='\0';
strcat(ans[i][j],ans[i+1][j-1]);
k=strlen(ans[i+1][j-1]);
ans[i][j][k+1]=s[j];
ans[i][j][k+2]='\0';
}
for(k=i;k<j;k++)
if(dp[i][j]>dp[i][k]+dp[k+1][j])
{
dp[i][j]=dp[i][k]+dp[k+1][j];
strcpy(ans[i][j],ans[i][k]);
strcat(ans[i][j],ans[k+1][j]);
}
}
cout<<ans[0][n]<<endl;
}
else printf("\n");
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator