題意：給你一串()[]括號(hào)，要你求出這串括號(hào)的最大匹配個(gè)數(shù)。如'('與')'匹配，為2個(gè)，'['與']'匹配，為2個(gè)

思路：區(qū)間dp

狀態(tài)方程：

if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')dp[i][j]=dp[i+1][j-1]+2; dp[i][j]=max{dp[i][k]+dp[k+1][j]};（k>i&&k<j） 代碼：（g++） #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> #include <vector> #include <set> #include <map> #include <queue> #include <stdlib.h> #include <string.h> #include <iomanip> #define N 10005<<1 #define INF 10000000 #define LL long long #define eps 10E-9 #define mem(a)? memset(a,0,sizeof(a)) #define mem1(a)? memset(a,-1,sizeof(a)) #define w(a)?? while(a) #define s(a)?? scanf("%d",&a) #define ss(a,b)?? scanf("%d%d",&a,&b) #define sss(a,b,c)?? scanf("%d%d%d",&a,&b,&c) #define PI acos(-1.0) using namespace std; int dp[101][101]; int main(){string s;w(cin>>s){mem(dp);if(s[0] == 'e') break;int len = s.length();for(int i=1; i<len; i++){for(int j=0,k=i; k<len; j++,k++){if(s[j] == '('&& s[k] == ')' || s[j] == '[' && s[k] == ']') dp[j][k] = dp[j+1][k-1] + 2;for(int l=j; l<k ; l++) dp[j][k] = max(dp[j][k], dp[j][l] + dp[l+1][k]);}}cout<<dp[0][len-1]<<endl;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/llguanli/p/8510516.html

總結(jié)

以上是生活随笔為你收集整理的poj 2955 区间dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。