POJ 1141 Brackets Sequence
9330 ワード
括弧の序列、劉汝佳黒書の経典の例題.しかし、この問題は私たちが最後に得たカッコを追加した最も少ないシーケンスを出力します.
出力シーケンスは確かに面倒で、問題解を参考にしてやっと無理に書いたので、後でこの問題をもう一度叩かなければなりません.
出力シーケンスは確かに面倒で、問題解を参考にしてやっと無理に書いたので、後でこの問題をもう一度叩かなければなりません.
/*Accepted 288K 32MS C++ 1862B 2012-07-23 11:46:07*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define o -2
#define lr -3
const int MAXN = 105;
int f[MAXN][MAXN], record[MAXN][MAXN];
char s[MAXN];
const int inf = 0x3f3f3f3f;
bool judge( int l, int r)
{
if( s[l] == '(' && s[r] == ')' || s[l] == '[' && s[r] == ']')
return true;
return false;
}
int dps(int l, int r)
{
int &ans = f[l][r], i;
if(ans != inf)
return ans;
if(l > r)
return 0;
if(l == r)
return record[l][r] = o, ans = 1;
for( i = l; i < r; i ++)
if( dps(l, i) + dps(i + 1, r) < ans)
ans = f[l][i] + f[i + 1][r], record[l][r] = i;
if( judge(l, r) && dps(l + 1, r - 1) < ans)
ans = f[l + 1][r - 1], record[l][r] = lr;
return ans;
}
void print(int l, int r)
{
switch( record[l][r])
{
case o :{
if( s[l] == '(' || s[l] == '[')
{
printf( "%c", s[l]);
print( l + 1, r);
printf( s[l] == '(' ? ")" : "]");
}
else
{
printf(s[l] == ')' ? "(" : "[");
printf("%c", s[l]);
print(l + 1, r);
}
break;
}
case lr:{
printf( "%c", s[l]);
print(l + 1, r - 1);
printf( "%c", s[r]);
break;
}
case -1:
return;
default:
print( l, record[l][r]), print(record[l][r] + 1, r);
break;
}
}
int main()
{
while( scanf( "%s", s + 1) == 1)
{
memset(f, 0x3f, sizeof f);
memset(record, -1, sizeof record);
dps(1, strlen(s + 1));
print(1, strlen(s + 1));
printf( "
");
}
return 0;
}