首页 > 其他 > 详细

POJ 2955 Brackets 区间DP

时间:2019-12-09 00:49:52      阅读:97      评论:0      收藏:0      [点我收藏+]

dp[x][y]表示[x,y]里的最大匹配,如果s[x]和s[y]匹配,那么dp[x][y] = dp[x + 1][y - 1] + 2。然后对于每个区间都试图将其拆成两半。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 char s[200];
 6 int dp[200][200];
 7 int dfs(int x,int y)
 8 {
 9     if (x >= y)
10         return 0;
11     if (dp[x][y] != -1)
12         return dp[x][y];
13     if ((s[x] == ( && s[y] == )) || (s[x] == [ && s[y] == ]))
14         dp[x][y] = dfs(x + 1,y - 1) + 2;
15     for (int i = x;i <= y - 1;i++)
16         dp[x][y] = max(dp[x][y],dfs(x,i) + dfs(i + 1,y));
17     return dp[x][y];
18 }
19 int main()
20 {
21     while (scanf("%s",s + 1) > 0)
22     {
23         memset(dp,-1,sizeof(dp));
24         if (s[1] == e)
25             break;
26         int len = strlen(s + 1);
27         printf("%d\n",dfs(1,len)); 
28     }
29     return 0;
30 }

 

POJ 2955 Brackets 区间DP

原文:https://www.cnblogs.com/iat14/p/12008515.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!