首页 > 代码库 > poj2955 区间dp
poj2955 区间dp
题目链接:http://poj.org/problem?id=2955
题意:给定字符串 求括号匹配最多时的子串长度。
区间dp,状态转移方程: dp[i][j]=max ( dp[i][j] , 2+dp[i+1][k-1]+dp[k+1][j] );
代码:
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; #define ll long long const int maxn=5e4+5; const int INF=0x3f3f3f3f; int dp[105][105]; char str[105]; int Find(int x,int y){ if((str[x]==‘(‘ && str[y]==‘)‘) || (str[x]==‘[‘ && str[y]==‘]‘)) return 2; else return 0; } int main(){ while(cin>>str && strcmp(str,"end")){ memset(dp,0,sizeof(dp)); int n=strlen(str); for(int d=1;d<n;d++) for(int i=0;i+d<n;i++){ int j=i+d; for(int k=i;k<=j;k++) dp[i][j]=max(dp[i][j],Find(i,k)+dp[i+1][k-1]+dp[k+1][j]); } printf("%d\n",dp[0][n-1]); } return 0; }
poj2955 区间dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。