Cod sursa(job #2145139)

Utilizator sergiudnyTritean Sergiu sergiudny Data 27 februarie 2018 09:49:18
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#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;
}