本文主要是介绍poj 1141(Brackets Sequence)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
黑书上DP第一道题，但这题要考虑输出。书上分了四种情况考虑，但我觉得只要考虑两种就行了(分为两个合法串和不分，然后设一个标志数组pre记录分开的位置)，这样输出更方便。第一种情况s[i]='('&&s[j]=')' 或者s[i]='['&&s[j]=']'，则d[i][j]=d[i+1][j-1]，则i,j处不需要添加括号,做一标记pre[i][j]=-1即可。第二种情况则把s[i]..s[j]分成两段考虑，枚举i,j中间的点k,i=<k<j，然后取d[i][j]=min(d[i][j],d[i][k]+d[k+1][j])，再对所取得k进行标记pre[i][j]=k。
然后输出也主要是分为上面两种情况。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char str[105];
int dp[101][101];
int pre[101][101];
void print(int i,int j)
{
if (i>j)
return;
if (i==j)
{
if (str[i]=='('||str[j]==')')
{
printf("()");
}
else
{
printf("[]");
}
return ;
}
if (pre[i][j]==-1)
{
printf("%c",str[i]);
print(i+1,j-1);
printf("%c",str[j]);
}
else
{
print(i,pre[i][j]);
print(pre[i][j]+1,j);
}
}
int main()
{
int i,j,p,k,len;
while (gets(str))
{
len=strlen(str);
for (i=0;i<len;i++)
dp[i][i]=1;
for (p=1;p<len;p++)
{
for (i=0;i+p<len;i++)
{
int j=i+p;
dp[i][j]=9999999;
if ((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
{
dp[i][j]=dp[i+1][j-1];
}
pre[i][j]=-1;
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];
pre[i][j]=k;
}
}
}
}
print(0,len-1);
printf("\n");
}
return 0;
}这篇关于poj 1141(Brackets Sequence)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
