POJ1141 ZOJ1463 Brackets Sequence 经典动态规划区间DP

对于这道题目WA的我想说：老子裤子都脱了，你就给我看这个？！开始做的时候，随意看了一下案例，就是左右括号可以匹配，题目给的字符串可能不是完全都有匹配的比如 (([]),这里就是差了一个),应该补全了输出 (([]))

思路还是比较简单的，区间dp,dp[i][j]表示区间 i 到j之间的匹配数，在这里有特殊情况的就是这个区间是一个闭合区间，要判断区间两端的字符是否可以刚好匹配,若可以匹配状态转移就多了一个 dp[i][j] = max(dp[i][k]+dp[k+1][j],dp[i+1][j-1]+1),若不能匹配就是dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);

若是两端可以匹配的，而且两端匹配了导致的dp值最大那么就标记一下，mark[i][j] = -1,否则就mark[i][j] = k，这样把所有区间都dp一遍，回头再用DFS寻找，若是两端匹配导致值最大的那么就直接输出这个字符标记一下，继续往更小的区间去搜索，否则就分开两个区间搜索 [i,k] [k+1,j],

由于值区间dp，所以被标记的就是本来就有匹配的，那么直接输出这个字符，否则就输出一对匹配的字符

思路是对的，但是一直WA啊，改啊改啊，但是还是WA，觉得思路非常清晰也很正确啊，经典的区间DP题目啊，后来看看大牛的博客，发现思路都是一样的啊，没什么区别，搞了两个半小时，实在受不了了，后来发现别人输入用的是getline，我抱着尝试的心态，试了改一下，居然过了，无语，去看看getline是什么玩意了

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
           #include
           
             #include
            
              #include
             
               #include
              
                #define ll long long #define eps 1e-7 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector
               
                 > G; //typedef pair
                
                  P; //vector
                 
                   > ::iterator iter; // //map
                  
                   mp; //map
                   
                    ::iterator p; //#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin) //#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout) // //void TestArray() //{ // char chs[] = {'a', 'd', 'c', 'e', 'b'}; // int count = sizeof(chs)/sizeof(char); // // next_permutation(chs+0, chs + count); // // printf("TestArray:\n"); // for(int i = 0; i < count; i++) { // printf("%c\t", chs[i]); // } // // printf("\n"); //} // //void TestVector() //{ // char chs[] = {'a', 'd', 'c', 'e', 'b'}; // int count = sizeof(chs)/sizeof(char); // vector
                    
                      vChs(chs, chs + count); // // next_permutation(vChs.begin(), vChs.end()); // // printf("TestVector:\n"); // vector
                     
                      ::iterator itr; // for(itr = vChs.begin(); itr != vChs.end(); itr++) { // printf("%c\t", *itr); // } // printf("\n"); //} // //int main(int argc, char *argv[]) //{ // TestArray(); // printf("\n"); // TestVector(); // // system("PAUSE"); // // return EXIT_SUCCESS; //} int dp[100 + 5][100 + 5]; int mark[100 + 5][100 + 5]; int pos[100 + 5]; void clear() { memset(dp,0,sizeof(dp)); for(int i=0;i<105;i++) for(int j=0;j<105;j++) mark[i][j] = -2; memset(pos,0,sizeof(pos)); } void dfs(int i,int j) {//倒回去搜索过程超级简单，就是DP过程嘛 if(mark[i][j] == -1) {//闭区间两头可以匹配 pos[i] = 1; pos[j] = 1; dfs(i+1,j-1); } else if(mark[i][j] >= 0) { dfs(i,mark[i][j]); dfs(mark[i][j]+1,j); } else return ; } int main() { string s; while(getline(cin,s)) { clear(); int i = 0; int j = 0; int k = 0; while(k < s.length()) { if(i == j) { i++; j++; if(j == s.length()) { i = 0; k++; j = k; } continue; } if((s[i] == '[' && s[j] == ']') || (s[i] == '(' && s[j] == ')')) {//闭区间两头可以匹配 for(int l=i;l

POJ1141 ZOJ1463 Brackets Sequence 经典动态规划 区间DP