poj 1141 动态规划进行括号匹配

思路:黑书的例题

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define Maxn 1010
using namespace std;
int dp[Maxn][Maxn],v[Maxn][Maxn];
char str[Maxn];
void Out(int s,int e)
{
if(s>e)
return ;
if(s==e)
{
if(str[s-]=='('||str[s-]==')')
printf("()");
else
printf("[]");
return ;
}
if(v[s][e]==-)
{
printf("%c",str[s-]);
Out(s+,e-);
printf("%c",str[e-]);
return ;
}
Out(s,v[s][e]);
Out(v[s][e]+,e);
}
int main()
{
int n,i,j,t,k;
memset(dp,,sizeof(dp));
memset(v,-,sizeof(v));
scanf("%s",str);
n=strlen(str);
for(i=;i<=n;i++)
dp[i][i]=,dp[i][i-]=;
for(i=;i<=n;i++)
for(j=i-;j>=;j--){
if(str[i-]==')'&&str[j-]=='('||str[i-]==']'&&str[j-]=='[')
{
if(dp[i-][j+]<dp[i][j])
dp[i][j]=dp[i-][j+],v[j][i]=-;
}
else
{
if(dp[i-][j]<dp[i][j+])
dp[i][j]=dp[i-][j]+,v[j][i]=i-;
else
dp[i][j]=dp[i][j+]+,v[j][i]=j;
}
for(k=j;k<i;k++)
{
if(dp[i][k+]+dp[k][j]<dp[i][j])
dp[i][j]=dp[i][k+]+dp[k][j],v[j][i]=k;
}
}
Out(,n);
printf("\n");
return ;
}
上一篇:javascript 仿面向对象编程实例代码(私有,公共变量。。。)


下一篇:xftp6提示要继续使用此程序,您必须应用最新的更新