http://poj.org/problem?id=1141
DP, 記錄路徑。
#?include?<stdio.h>
#?include?<string.h>
#?define?N?205
#?define?INF?1000000000
#?define?Mid?(1?<<?10)
#?define?Lft?(1?<<?9?)
#?define?Rgt?(1?<<?8?)
char?buf[N];
int?f[N][N],?p[N][N];
int?dp(int?x,?int?y)
{
????????????????int?&?ans?=?f[x][y];
????????????????if?(ans?!=?-1)?return?ans;
????????????????if?(x?>?y)?return?ans?=?0;
????????????????ans?=?INF;
????????????????if?(?(buf[x]=='('&&buf[y]==')')?||
?????????????????????(buf[x]=='['&&buf[y]==']')?)
????????????????{
????????????????????????????????if?(ans?>?dp(x+1,?y-1))
????????????????????????????????{
????????????????????????????????????????????????p[x][y]?=?Mid;
????????????????????????????????????????????????ans?=?f[x+1][y-1];
????????????????????????????????}
????????????????}
????????????????if?(?buf[x]=='('?||?buf[x]=='['?)
????????????????{
????????????????????????????????if?(ans?>?dp(x+1,?y)+1)
????????????????????????????????{
????????????????????????????????????????????????p[x][y]?=?Rgt;
????????????????????????????????????????????????ans?=?f[x+1][y]?+?1;
????????????????????????????????}
????????????????}
????????????????if?(?buf[y]==')'?||?buf[y]==']'?)
????????????????{
????????????????????????????????if?(ans?>?dp(x,?y-1)+1)
????????????????????????????????{
????????????????????????????????????????????????p[x][y]?=?Lft;
????????????????????????????????????????????????ans?=?f[x][y-1]?+?1;
????????????????????????????????}
????????????????}
????????????????for?(int?i?=?x;?i?<?y;?++i)
????????????????{
????????????????????????????????if?(ans?>?dp(x,?i)+dp(i+1,?y))
????????????????????????????????{
????????????????????????????????????????????????p[x][y]?=?i;
????????????????????????????????????????????????ans?=?f[x][i]?+?f[i+1][y];
????????????????????????????????}
????????????????}
????????????????return?ans;
}
void?print(int?s,?int?t)
{
????????????????switch(p[s][t])
????????????????{
????????????????????????????????case?Mid:
????????????????????????????????{
????????????????????????????????????????????????putchar(buf[s]),?print(s+1,?t-1),?putchar(buf[t]);
????????????????????????????????????????????????break;
????????????????????????????????}
????????????????????????????????case?Lft:
????????????????????????????????{
????????????????????????????????????????????????if?(buf[t]?==?')')
????????????????????????????????????????????????????????????????putchar('('),?print(s,?t-1),?putchar(')');
????????????????????????????????????????????????else
????????????????????????????????????????????????????????????????putchar('['),?print(s,?t-1),?putchar(']');
????????????????????????????????????????????????break;
????????????????????????????????}
????????????????????????????????case?Rgt:
????????????????????????????????{
????????????????????????????????????????????????if?(buf[s]?==?'(')
????????????????????????????????????????????????????????????????putchar('('),?print(s+1,?t),?putchar(')');
????????????????????????????????????????????????else
????????????????????????????????????????????????????????????????putchar('['),?print(s+1,?t),?putchar(']');
????????????????????????????????????????????????break;
????????????????????????????????}
????????????????????????????????case?0:
????????????????????????????????{
????????????????????????????????????????????????for?(int?i?=?s;?i?<=?t;?++i)
????????????????????????????????????????????????????????????????putchar(buf[i]);
????????????????????????????????????????????????break;
????????????????????????????????}
????????????????????????????????default:
????????????????????????????????{
????????????????????????????????????????????????print(s,?p[s][t]),?print(p[s][t]+1,?t);
????????????????????????????????????????????????break;
????????????????????????????????}
????????????????}
}
int?main()
{
????????????????int?n;
????????????????buf[0]?=?0,?scanf("%s",?buf+1);
????????????????memset(f,?-1,?sizeof(f));
????????????????memset(p,?0,?sizeof(p));
????????????????n?=?strlen(buf+1);
????????????????dp(1,?n),?print(1,?n),?putchar('\n');
????????????????return?0;
}
posted on 2012-10-11 13:57
yajunw 閱讀(258)
評論(0) 編輯 收藏 引用