POJ 2955 区间DP

本文主要是介绍POJ 2955 区间DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求最多能匹配的括号数*2

#include "stdio.h"
#include "string.h"int max(int a,int b)
{if (a<b) return b;else return a;
}int judge(char a,char b)
{if (a=='(' && b==')') return 1;if (a=='[' && b==']') return 1;return 0;
}
int main()
{int i,j,s,e,n,k;char str[110];int dp[110][110],ans[110];while (gets(str)){if (str[0]=='e') break;memset(dp,0,sizeof(dp));n=strlen(str);for (i=0;i<n-1;i++)if (judge(str[i],str[i+1])==1)dp[i][i+1]=2;for (i=3;i<=n;i++)for (j=0;j<n-i+1;j++){s=j; e=i+j-1;if (judge(str[s],str[e])==1) dp[s][e]=max(dp[s][e],2+dp[s+1][e-1]);for (k=s;k<=e-1;k++)dp[s][e]=max(dp[s][e],dp[s][k]+dp[k+1][e]);}memset(ans,0,sizeof(ans));for (i=1;i<n;i++){ans[i]=dp[0][i];for (j=1;j<=i;j++){ans[i]=max(ans[i],ans[j-1]+dp[j][i]);}}printf("%d\n",ans[n-1]);}return 0;
}

这篇关于POJ 2955 区间DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---