poj2955(区间dp)-白红宇

poj2955(区间dp)

阅读量：6442 次

发布时间：2019-06-23

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

题目连接：

题意：给一个由()[]四种字符任意排列组成的字符串，求最长合法的不连续字串的长度。

分析：如果找到一对匹配的括号[xxx]oooo，就把区间分成两部分，一部分是xxx，一部分是ooo，然后以此递归直到区间长度为<=1.

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #define LL long long#define mod 100000000#define inf 0x3f3f3f3f#define eps 1e-9#define N 100010#define FILL(a,b) (memset(a,b,sizeof(a)))#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;int dp[110][110];char str[110];bool judge(int i,int j){ return (str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']');}int dfs(int l,int r){ if(dp[l][r]!=-1)return dp[l][r]; if(l>=r)return 0; int temp=dfs(l+1,r); for(int i=l+1;i<=r;i++) { if(judge(l,i)) temp=max(temp,dfs(l+1,i-1)+dfs(i+1,r)+2); } return dp[l][r]=temp;}int main(){ int n; while(scanf("%s",str+1)>0) { if(strcmp(str+1,"end")==0)break; FILL(dp,-1);n=strlen(str+1); printf("%d\n",dfs(1,n)); }}