当前位置：网站首页>POJ - 2955 brackets interval DP

POJ - 2955 brackets interval DP

2022-04-23 06:21:00 【Bzdhxs_ nt】

subject link

Ideas

Classical interval d p dp dp The topic of transfer mode has been given

consider d p [ i ] [ j ] dp[i][j] dp[i][j] It means that [ i , j ] [i,j] [i,j] The number of bracket pairs that can be matched in the interval
State shift
f [ i ] [ j ] = f [ i + 1 ] [ j − 1 ] + c h e c k ( i , j ) ; f[i][j] = f[i+1][j-1] + check(i,j); f[i][j]=f[i+1][j−1]+check(i,j);
f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] ) ; f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]); f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);

Code 

int f[110][110];
string s;
bool chk(int i,int j){
    
    if((s[i] == '[' && s[j] == ']')||(s[i]=='(' && s[j]==')')) return true;
    return false;
}

signed main()
{
    
    
    while(cin >> s){
    
        if(s == "end") break;
        mem(f,0);
        int le = s.size();
        forr(len,2,le){
    

            for(int i = 0;i+len-1<le;i++){
    
                int j = i+len-1;
                f[i][j] = f[i+1][j-1]+chk(i,j);
                for(int k = i;k<j;k++) f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]);
            }
        }
        cout << f[0][le-1]*2 << endl;
    }
    return 0;

版权声明
本文为[Bzdhxs_ nt]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/04/202204210617219258.html

边栏推荐

猜你喜欢

随机推荐