http://poj.org/problem?id=1141
着题的难点不在于动态规划 而在于输出
其实想想也不难 DP 后根据最优解进行递归找需要匹配的括号就可以了
代码及其注释：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<cmath>
#define LL long long
using namespace std;
const int N=105;
char s[N];
int mm[N][N];//l到r所需最少匹配
bool add[N];//是否需要匹配
int dp(int l,int r)
{
if(l>r)
return 0;
if(mm[l][r]!=-1)
return mm[l][r];
if(l==r)//只有一个括号 必须匹配
{
mm[l][r]=1;
return mm[l][r];
}
if(l<r)//找最优
{
mm[l][r]=N;
if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
{
mm[l][r]=dp(l+1,r-1);
}
for(int i=l;i<r;++i)
{
mm[l][r]=min(mm[l][r],dp(l,i)+dp(i+1,r));
}
return mm[l][r];
}
return mm[l][r];
}
void findadd(int l,int r)//找符合条件的最优向下递归 找需要匹配的括号
{
if(l>r)
return ;
if(l==r)
add[l]=true;
if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
{
if((l>r&&mm[l][r]==0)||mm[l][r]==mm[l+1][r-1])
{
findadd(l+1,r-1);
return;
}
}
for(int i=l;i<r;++i)
{
if(mm[l][i]+mm[i+1][r]==mm[l][r])
{
findadd(l,i);
findadd(i+1,r);
return ;
}
}
}
int main()
{
while(gets(s))
{
int n=strlen(s);
memset(mm,-1,sizeof(mm));
memset(add,false,sizeof(add));
dp(0,n-1);
findadd(0,n-1);
for(int i=0;i<n;++i)
{
if(add[i])
{
if(s[i]=='(')
printf("%c)",s[i]);
if(s[i]==')')
printf("(%c",s[i]);
if(s[i]=='[')
printf("%c]",s[i]);
if(s[i]==']')
printf("[%c",s[i]);
continue;
}
printf("%c",s[i]);
}
printf("\n");
}
return 0;
}
