POJ 2955 Brackets（区间DP）-蒲公英云

POJ 2955 Brackets（区间DP）

快来打我* 2023-06-04 13:57 132阅读 0赞

嗯…

题目链接：http://poj.org/problem?id=2955

一道比较经典的区间dp，注意首先更新dp，然后再转移，转移的时候并没有什么代价，即dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]

AC代码：

1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 char s[105];
 9 int dp[1005][1005];
10 
11 inline bool judge(int x, int y){
12     if(s[x] == '(' && s[y] == ')') return 1;
13     if(s[x] == '[' && s[y] == ']') return 1;
14     return 0;
15 }//判断 
16 
17 int main(){
18     while(~scanf("%s", s)){
19         memset(dp, 0, sizeof(dp));
20         if(s[0] == 'e') break;
21         int len = strlen(s);
22         for(int l = 1; l < len; l++){
23             for(int i = 0; i < len; i++){
24                 int j = i + l;
25                 if(j > len) break;
26                 if(judge(i, j)){
27                     if(j - i == 1) dp[i][j] = 2;
28                     else dp[i][j] = dp[i + 1][j - 1] + 2;
29                 }//更新dp 
30                 for(int k = i; k < j; k++){
31                     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]);
32                 }//转移 
33             }
34         }
35         printf("%d\n", dp[0][len - 1]);
36     }
37     return 0;
38 }