Pagini recente » Cod sursa (job #629813) | Cod sursa (job #2083609) | Cod sursa (job #1690385) | Cod sursa (job #830249) | Cod sursa (job #2145139)
#include <bits/stdc++.h>
#define DM 1005
#define pb push_back
#define INF 0x3f3f3f3f
using namespace std;
ifstream fin("test.in");
ofstream fout("test.out");
string v;
int dp[DM][DM];
void afis(int st,int dr){
if(dr<st) return;
if(dp[st][dr]==dp[st+1][dr]){
if(v[st]==v[dr]){
fout<<v[st];
afis(st+1,dr-1);
fout<<v[dr];
} else {
fout<<v[st];
afis(st+1,dr);
fout<<(v[st]=='('?')':']');
}
} else if(dp[st][dr]==dp[st+1][dr]+1){
fout<<v[st]<<v[st+1];
afis(st+2,dr);
}
}
int getdp(int st, int dr){
if(st>dr) return 0;
if(dp[st][dr]!=INF)
return dp[st][dr];
if(v[st]==']' || v[st]==')'){
return dp[st][dr]=1+getdp(st+1,dr);
}
vector<int>last;
if(st=='('){
for(int i=st+1;i<=dr;++i) if(v[i]==')')
last.pb(i);
} else if(st=='['){
for(int i=st+1;i<=dr;++i) if(v[i]==']')
last.pb(i);
}
for(auto i:last)
dp[st][dr]=min(getdp(st+1,i-1)+getdp(i+1,dr),dp[st][dr]);
dp[st][dr]=min(dp[st][dr],getdp(st+1,dr)+1);
dp[st][dr]=min(dp[st][dr],getdp(st+2,dr)+1);
return dp[st][dr];
}
int main()
{
fin>>v;
memset(dp,INF,sizeof(dp));
getdp(0,v.size()-1);
afis(0,v.size()-1);
return 0;
}