首页 > 代码库 > HDU 3351 Seinfeld（括号匹配）

HDU 3351 Seinfeld（括号匹配）

2024-07-18 05:38:26   212人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3351

解题报告：输入一个只有‘{‘跟‘}‘的字符串，有两种操作，一种是把‘{‘变成‘}‘，另一种是‘}‘变成‘{‘，问你要把这个字符串的括号变成合法的最少需要多少次操作。

在刷DP专题，居然有个这个题目，看起来也像是DP，一直在想用DP怎么做，始终没做出来，最后试下直接字符串匹配居然A了。跟普通的字符串匹配的区别就是

在插入‘}‘这个的时候判断一下栈是不是为空，如果栈为空，则把这个‘}‘改为‘{‘再插入，最后判断栈是不是空，如果栈不为空，则剩下的一定都是‘{‘这个，所以只要把一般的

‘{‘这个改成‘}‘这个就可以了，所以还要加上一般的栈长度才是最后答案。

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 #include<deque> 6 using namespace std; 7 #define maxn 2005 8 char str[maxn]; 9 int dp[maxn][maxn];10 int judge(int i,int j)11 {12     int tot = 0;13     if(str[i] != ‘{‘) tot++;14     if(str[j] != ‘}‘) tot++;15     return tot;16 }17 deque<char> que;18 int main()19 {20 //    freopen("in.txt","r",stdin);21 //    freopen("out.txt","w",stdout);22     int kase = 1;23     while(scanf("%s",str)!=EOF)24     {25         int len = strlen(str),ans = 0;26         if(str[0] == ‘-‘) break;27         que.clear();28         for(int i = 0;i < len;++i)29         {30             if(str[i] == ‘{‘)31             que.push_front(str[i]);32             else33             {34                 if(que.empty())35                 {36                     que.push_front(‘{‘);37                     ans++;38                 }39                 else que.pop_front();40             }41         }42         if(!que.empty())43         ans += (que.size()/2);44         printf("%d. %d\n",kase++,ans);45     }46     return 0;47 }48 /*        memset(dp,0,sizeof(dp));49         for(int i = len-1;i >= 0;--i)50         for(int j = i + 1;j < len;j+=2)51         {52             dp[i][j] = 0x7fffffff;53             if(j == i + 1) dp[i][j] = judge(i,j);54             else55             {56                 dp[i][j] = min(dp[i+1][j-1]+judge(i,j),dp[i][j]);57                 if(j >= 2)58                 dp[i][j] = min(dp[i][j-2]+judge(j-1,j),dp[i][j]);59                 if(i+2 < len)60                 dp[i][j] = min(dp[i+2][j]+judge(i,i+1),dp[i][j]);61             }62         }63         printf("%d. %d\n",kase++,dp[0][len-1]);64     }65     return 0;66 }*/
View Code

 


联系
我们