现在的位置: 首页 > 算法 > 正文

动态规划 Brackets Sequence poj 1141

2018年05月02日 算法 ⁄ 共 2219字 ⁄ 字号 评论关闭

题目连接:http://poj.org/problem?id=1141

题目大意:给出一串括号序列(只包含小括号和中括号),求包含次子序列的长度最小的regular brackets sequence。其中regular brackets sequence定义如下:

1.空序列是一个regular brackets sequence;

2.如果s是一个regular brackets sequence,那么[s]也是一个regular brackets sequence,(s)也是一个regular brackets sequence。

3.如果A、B都是regular brackets sequence,那么AB也是一个regular brackets sequence。

例如:()、[]、([])、([])()[()]都是regular brackets sequence

而[[[、(((、([)]则都不是regular brackets sequence

其中一([)]为例,包含它最小的regular brackets sequence有两个:()[()]、([])[],只需输出一个就行。

代码:

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4.   
  5. using namespace std;  
  6.   
  7. char str[105];  
  8. int dp[101][101];//i到j之间加成为regular brackets sequence需要加入的最少字符数  
  9. int tag[101][101];//用来做标记 记录最少字符时的是那种情况  
  10. int len;  
  11.   
  12. void print(int s,int e)  
  13. {  
  14.     if (s>e)return;  
  15.     if (s==e)  
  16.     {  
  17.         if (str[s]=='(' || str[s]==')')  
  18.         {  
  19.             printf("()");  
  20.         }  
  21.         else  
  22.         {  
  23.             printf("[]");  
  24.         }  
  25.         return ;  
  26.     }  
  27.     if (tag[s][e]==-1)  
  28.     {  
  29.         printf("%c",str[s]);  
  30.         print(s+1,e-1);  
  31.         printf("%c",str[e]);  
  32.     }  
  33.     else  
  34.     {  
  35.         print(s,tag[s][e]);  
  36.         print(tag[s][e]+1,e);  
  37.     }  
  38. }  
  39.   
  40. int main()  
  41. {  
  42.     while (gets(str))  
  43.     {  
  44.         len = strlen(str);  
  45.         for (int i=0;i<len;i++)  
  46.         {  
  47.             dp[i][i]=1;//初始  
  48.             dp[i+1][i]=0;//下面在进行DP时,i=j+1时,i=i+1、j=j-1会造成i=j+1  
  49.         }  
  50.         for (int st=1;st<len;st++)  
  51.         {  
  52.             for (int i=0;i+st<len;i++)  
  53.             {  
  54.                 int j=i+st;  
  55.                 int temp=9999999;  
  56.                 if ((str[i]=='(' && str[j]==')')||(str[i]=='[' && str[j]==']'))  
  57.                 {  
  58.                     temp=dp[i+1][j-1];//第一种情况(s)或[s]  
  59.                 }  
  60.                 tag[i][j]=-1;  
  61.                 for (int k=i;k<j;k++)//第二种情况,枚举i到j之间的k 即AB  
  62.                 {  
  63.                     int res=dp[i][k]+dp[k+1][j];  
  64.                     if (res<temp)  
  65.                     {  
  66.                         temp=res;  
  67.                         tag[i][j]=k;  
  68.                     }  
  69.                 }  
  70.                 dp[i][j]=temp;  
  71.             }  
  72.         }  
  73.         print(0,len-1);//根据标记情况进行回溯  
  74.         printf("\n");  
  75.     }  
  76.     return 0;  
  77. }  

抱歉!评论已关闭.