首页 > 代码库 > poj 1141

poj 1141

2024-11-24 02:07:39   203人阅读

第一个区间dp题，果断百度的

蛮好理解，这里直接粘贴别人的题解啦，d是区间内需要添加的括号数

对于任何s[i]..s[j]应该分为两种情况考虑，一种是s[i]=‘(‘&& amp;s[j]=‘)‘ 或者s[i]=‘[‘&&s[j]=‘]‘，如果是这种情况，则d[i][j]=d[i+1][j-1]，则i,j处不需要添加括号。做 一标记v[i][j]=-1;即可。还有一种情况就是上述条件不满足，则可以把s[i]..s[j]分成两段考虑，枚举i,j中间的点k,i=< k<j;即可。然后取d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);同时应该对所取得k进行标记v[i] [j]=k。

　　然后就是输出问题，对任意的s[i]..s[j]，对其输出，如果i>j则输出 结束。否则分几种情况考虑：1.i=j;则此时i,j指的就是一个单个字符，如果s[i]=‘(‘or‘)‘直接输出一对括号即可。等于‘[‘同上。但是 一般的情况都是i,j中间还有字符，要分两种情况，如果v[i][j]=-1;即标记时s[i]、s[j]是一对，此时输出 s[i],s[i+1]..s[j-1],s[j]即可。如果更一般的情况即v[i][j]不等于-1的时候就是说s[i]..s[j]已经在i,j中间 分开，那么仍然是递归输出s[i]...s[v[i][j]],s[v[i][j]+1]...s[j]即可。至此输出完成。
 
 1 #include<iostream> 2 #include<string> 3 #include<fstream> 4 #include<cstring> 5 using namespace std; 6 char s[101]; 7 int d[101][101],value[101][101],length; 8 void fun() 9 {10     for(int p=0;p<length;p++)d[p][p]=1;       //一个的话只需要一个就能匹配11     for(int tem=1;tem<length;tem++)     //枚举区间长度12         for(int i=0;i<length-tem;i++) //i的起始位置13         {14             int j=tem+i;15             d[i][j]=99999;16             if((s[i]==‘(‘&&s[j]==‘)‘)||(s[i]==‘[‘&&s[j]==‘]‘))//1@17             {18                 d[i][j]=d[i+1][j-1];19                 value[i][j]=-1;20             }21             for(int k=i;k<j;k++)22                 if(d[i][j]>d[i][k]+d[k+1][j])23                 {24                     d[i][j]=d[i][k]+d[k+1][j];25                     value[i][j]=k;26                 }27         }28         return;29 }30 void printpath(int i,int j)31 {32     if(i>j)return;33     else if(i==j)34     {35         if(s[i]==‘(‘||s[i]==‘)‘)printf("()");36         if(s[i]==‘[‘||s[i]==‘]‘)printf("[]");37     }else if(value[i][j]==-1)38     {39         printf("%c",s[i]);40         printpath(i+1,j-1);41         printf("%c",s[j]);42     }else {43         printpath(i,value[i][j]);44         printpath(value[i][j]+1,j);45     }46     return;47 }48 int main()49 {50     //freopen("1.in","r",stdin);51     while(scanf("%s",s)!=EOF)52     {53         memset(d,0,sizeof(d));54         length=strlen(s);55         fun();56         printpath(0,length-1);57         printf("\n");58     }59     return 0;60 }

 

poj 1141


联系
我们