区间dp括号匹配-白红宇

区间dp括号匹配

阅读量：6418 次

发布时间：2019-06-23

本文共 4793 字，大约阅读时间需要 15 分钟。

匹配则加一，不需要初始化

1 //#include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                
                 12 #include
                 
                  13 #include
                  
                   14 #include
                   
                    15 #include
                    
                     16 #include
                     
                      17 #define a first18 #define b second19 #define mp make_pair20 #define pb push_back21 #define pw(x) (1ll << (x))22 #define sz(x) ((int)(x).size())23 #define all(x) (x).begin(),(x).end()24 #define rep(i,l,r) for(int i=(l);i<(r);i++)25 #define per(i,r,l) for(int i=(r);i>=(l);i--)26 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)27 #define debug1(a)\28 cout << #a << " = " << a << endl;29 #define debug2(a,b)\30 cout << #a << " = " << a << endl;\31 cout << #b << " = " << b << endl;32 #define debug3(a,b,c) cout << #a << " = " << a << endl;\33 cout << #b << " = " << b << endl;\34 cout << #c << " = " << c << endl;35 #define debug4(a,b,c,d)\36 cout << #a << " = " << a << endl;\37 cout << #b << " = " << b << endl;\38 cout << #c << " = " << c << endl;\39 cout << #d << " = " << d << endl;40 #define debug5(a,b,c,d,e)\41 cout << #a << " = " << a << endl;\42 cout << #b << " = " << b << endl;\43 cout << #c << " = " << c << endl;\44 cout << #d << " = " << d << endl;\45 cout << #e << " = " << e << endl;46 #define eps 1e-947 #define PIE acos(-1)48 #define cl(a,b) memset(a,b,sizeof(a))49 #define fastio ios::sync_with_stdio(false);cin.tie(0);50 #define lson l , mid , ls51 #define rson mid + 1 , r , rs52 #define ls (rt<<1)53 #define rs (ls|1)54 #define INF 0x3f3f3f3f55 #define lowbit(x) (x&(-x))56 #define sqr(a) a*a57 #define ll long long58 #define vi vector
                      
                       59 #define pii pair
                       
                        60 using namespace std;61 //**********************************62 char s[107];63 int n;64 int dp[107][107];65 //**********************************66 bool match(int a,int b)67 {68 char x=s[a],y=s[b];69 return x=='['&&y==']'||x=='('&&y==')';70 }71 void solve()72 {73 FOR(len,2,n)FOR(l,1,n-len+1){74 int r=l+len-1;75 dp[l][r]=dp[l+1][r-1]+match(l,r); 76 rep(k,l,r){77 dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]);78 }79 }80 printf("%d\n",dp[1][n]<<1);81 }82 //**********************************83 int main()84 {85 while(~scanf("%s",s+1)&&s[1]!='e'){86 n=strlen(s+1);87 solve();88 }89 return 0;90 }

View Code

不匹配加一，注意初始化边界

1 //#include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
             8 #include
             
               9 #include
              
               10 #include
               
                11 #include
                
                 12 #include
                 
                  13 #include
                  
                   14 #include
                   
                    15 #include
                    
                     16 #include
                     
                      17 #define fi first18 #define se second19 #define mp make_pair20 #define pb push_back21 #define pw(x) (1ll << (x))22 #define sz(x) ((int)(x).size())23 #define all(x) (x).begin(),(x).end()24 #define rep(i,l,r) for(int i=(l);i<(r);i++)25 #define per(i,r,l) for(int i=(r);i>=(l);i--)26 #define FOR(i,l,r) for(int i=(l);i<=(r);i++)27 #define debug1(a)\28 cout << #a << " = " << a << endl29 #define debug2(a,b)\30 cout << #a << " = " << a << endl;\31 cout << #b << " = " << b << endl;32 #define debug3(a,b,c) cout << #a << " = " << a << endl;\33 cout << #b << " = " << b << endl;\34 cout << #c << " = " << c << endl;35 #define debug4(a,b,c,d)\36 cout << #a << " = " << a << endl;\37 cout << #b << " = " << b << endl;\38 cout << #c << " = " << c << endl;\39 cout << #d << " = " << d << endl;40 #define debug5(a,b,c,d,e)\41 cout << #a << " = " << a << endl;\42 cout << #b << " = " << b << endl;\43 cout << #c << " = " << c << endl;\44 cout << #d << " = " << d << endl;\45 cout << #e << " = " << e << endl46 #define eps 1e-947 #define PIE acos(-1)48 #define cl(a,b) memset(a,b,sizeof(a))49 #define fastio ios::sync_with_stdio(false);cin.tie(0);50 #define lson l , mid , ls51 #define rson mid + 1 , r , rs52 #define ls (rt<<1)53 #define rs (ls|1)54 #define INF 0x3f3f3f3f55 #define lowbit(x) (x&(-x))56 #define sqr(a) a*a57 #define ll long long58 #define vi vector
                      
                       59 #define pii pair
                       
                        60 using namespace std;61 //**********************************62 int a[507];63 int n;64 int dp[507][507];65 //**********************************66 bool match(int x,int y)67 {68 return a[x]==a[y];69 }70 void solve()71 {72 cl(dp,INF);73 FOR(i,1,n){74 dp[i][i]=1;75 if(a[i]==a[i+1])dp[i][i+1]=1;76 }77 FOR(len,2,n){78 FOR(l,1,n-len+1){79 int r=l+len-1;80 if(match(l,r)){81 if(r==l+1)dp[l][r]=1;82 else dp[l][r]=dp[l+1][r-1];83 }84 // if(match(l,r))dp[l][r]=min(dp[l][r],dp[l+1][r-1]);85 rep(k,l,r){86 dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);87 }88 }89 }90 printf("%d\n",dp[1][n]);91 }92 //**********************************93 int main()94 {95 cin>>n;96 FOR(i,1,n)cin>>a[i];97 solve();98 return 0;99 }