大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
取血怒。first blood,第一区间DP,这样第一次没有以某种方式在不知不觉中下降~~~
题目尽管是鸟语。但还是非常赤裸裸的告诉我们要求最大的括号匹配数。DP走起~
dp[i][j]表示区间[i,j]的最大匹配数。那么最重要的状态转移方程就是:
dp[i][j]=max(dp[i][k]+dp[k+1][j])
对啦,要先初始化边界啊。两步走~:
memset(dp,0,sizeof dp);
if str[i]==str[i+1] 则:dp[i][i+1]=2 请看—->> 该字符串 ( [ ] [ ] [ ) 非常好懂有木有
万恶的贴代码:
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int dp[110][110]; char s[110]; bool check(int i,int j)//推断是不是匹配的 { if(s[i]=='['&&s[j]==']') return true; if(s[i]=='('&&s[j]==')') return true; return false; } int main() { while(scanf("%s",s)!=EOF){ if(strcmp(s,"end")==0) break; int l=strlen(s); memset(dp,0,sizeof dp); for(int i=0;i<l;i++){ //初始化 if(check(i,i+1)){ dp[i][i+1]=2; } } for(int p=3;p<=l;p++){ //枚举区间长度 for(int i=0;i<=l-p;i++){ //枚举区间起点 int j=i+p-1; if(check(i,j)){ dp[i][j]=dp[i+1][j-1]+2; } for(int k=i;k<j;k++){ //将区间分成两段 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]); } } } cout<<dp[0][l-1]<<endl; } return 0; }
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116728.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...