[关闭]
@xunuo 2017-01-16T14:21:57.000000Z 字数 1986 阅读 1076

Brackets Sequence

Time limit 1000 ms Memory limit 65536 kB

区间DP

来源:
poj: poj 1141 Brackets Sequence
vjudge:c-Brackets Sequence


Description

Let us define a regular brackets sequence in the following way: 

1. Empty sequence is a regular sequence. 
2. If S is a regular sequence, then (S) and [S] are both     regular sequences. 
3. If A and B are regular sequences, then AB is a regular sequence. 

For example, all of the following sequences of characters are regular brackets sequences: 

(), [], (()), ([]), ()[], ()[()] 

And all of the following character sequences are not: 

(, [, ), )(, ([)], ([(] 

Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.

Input

The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.

Output

Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

Sample Input

([(]

Sample Output

()[()]

题意:

输入一串只有 '(' ')' '[' ']'的字符串,求最少加入多少个括号能够使它组成完整。输出完整的字符串

解题思路:

区间DP......
记得自己推一遍,,,你就明白了@_@
你自己是想不到的-_-||

完整代码:

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. using namespace std;
  5. #define inf 0x3ffffff
  6. char s[110];
  7. int dp[110][110],vis[110][110];
  8. void print(int i,int j)
  9. {
  10. if(i>j)
  11. return;
  12. if(i==j)
  13. {
  14. if(s[i]=='('||s[i]==')')
  15. printf("()");
  16. else if(s[i]=='['||s[i]==']')
  17. printf("[]");
  18. }
  19. else if(vis[i][j]==-1)
  20. {
  21. printf("%c",s[i]);
  22. print(i+1,j-1);
  23. printf("%c",s[j]);
  24. }
  25. else
  26. {
  27. print(i,vis[i][j]);
  28. print(vis[i][j]+1,j);
  29. }
  30. }
  31. int main()
  32. {
  33. gets(s);
  34. int len=strlen(s);
  35. for(int i=0;i<len;i++)
  36. dp[i][i]=1;
  37. for(int l=1;l<len;l++)
  38. for(int i=0;i<len-l;i++)
  39. {
  40. int j=l+i;
  41. dp[i][j]=inf;
  42. if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))
  43. {
  44. if(dp[i][j]>dp[i+1][j-1])
  45. {
  46. dp[i][j]=dp[i+1][j-1];
  47. vis[i][j]=-1;///表示s[i] 与s[j] 匹配时是最优的;
  48. }
  49. }
  50. for(int k=i;k<j;k++)
  51. {
  52. if(dp[i][j]>dp[i][k]+dp[k+1][j])
  53. {
  54. dp[i][j]=dp[i][k]+dp[k+1][j];
  55. vis[i][j]=k;///表示以k为分割点匹配时最优;
  56. }
  57. }
  58. }
  59. print(0,len-1);
  60. printf("\n");
  61. return 0;
  62. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注