poj 1141的动态规划题目是那种 背包问题的变形~

动态规划 d[i][i]=1
如果a[i]a[j]括号配对 d[i][j]=min(d[i+1][j-1],d[i][k]+d[k][j]) k=i...j
如果不配对 d[i][j]=min(d[i][k]+d[k][j]) k=i...j
最少添加的括号数就是d[1][n]
要是输出的话需要一个数组f[i][j]来表示i，j从哪断开 f[i][j]是-1的话表示不断开 i=j输出括号 i！=j 输出清答慎 c[i] 递归输出i+1 j-1 c[j]
#include
#include
#define min(a,b) ((a)<(b)?(a):(b))
int d[102][102];
int f[102][102];
char c[102];
void print(int low,int high)
{
if(low>high)
return;
if(f[low][high]==-1)
{
if(low==high)
{
if(c[low]=='('||c[low]==')')
printf("()");
else if(c[low]=='['||c[low]==']')
printf("[]");
}
else
{
printf("%c",c[low]);
print(low+1,high-1);
printf("%c"答敬,c[high]);
}
}
else
{
int t=f[low][high];
print(low,t);
print(t+1,high);
}
return;
}
int main()
{

scanf("%s",&c);
int l=strlen(c);
int i,j,k,p,temp;
memset(d, 0, sizeof(d));
memset(f, -1, sizeof(f));
for(i=0;i {
d[i][i]=1;
}
for(k=1;k<=l-1;++k)
{
for(i=0,j=k;j {
temp=200;
if((c[i]=='('&&c[j]==')')||(c[i]=='['&&c[j]==']'))
temp=min(temp,d[i+1][j-1]);

for(p=i;p {
if(temp>d[i][p]+d[p+1][j])
{
temp=d[i][p]+d[p+1][j];
f[i][j]=p;
}
}
d[i][j]=temp;

}
}
print(0,l-1);
printf("\n"举做);
return 0;

}