POJ2955 Brackets (区间DP)
2022/6/17 23:27:06
本文主要是介绍POJ2955 Brackets (区间DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
很好的区间DP题。
需要注意第一种情况不管是否匹配,都要枚举k来更新答案,比如:
“()()()”:dp[0][5]=dp[1][4]+2=4,枚举k,k=1时,dp[0][1]+dp[2][5]=6,最后取最大值6.
第一层d相当于“长度”的含义,第二层枚举i,j就可以用i+d表示,通过这种方式枚举区间左右端点。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<iostream> 7 using namespace std; 8 int dp[105][105]; 9 char s[105]; 10 11 bool match(int l,int r){ 12 if(s[l]=='('&&s[r]==')') return 1; 13 if(s[l]=='['&&s[r]==']') return 1; 14 return 0; 15 } 16 17 int main(){ 18 while(~scanf("%s",s)&&s[0]!='e'){ 19 int len=strlen(s); 20 memset(dp,0,sizeof(dp)); 21 for(int d=1;d<len;d++) 22 for(int i=0;i<len-d;i++){ 23 int j=i+d; 24 if(match(i,j))//括号成功匹配 25 dp[i][j]=dp[i+1][j-1]+2; 26 for(int k=i;k<j;k++)//不管匹配是否成功,都要进行这步操作,保证最优解 27 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]); 28 } 29 printf("%d\n",dp[0][len-1]); 30 } 31 return 0; 32 }
这篇关于POJ2955 Brackets (区间DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding
- 2024-06-23AI大模型企业应用实战(15)-langchain核心组件
- 2024-06-23AI大模型企业应用实战(16)-langchain核心组件
- 2024-06-23AI 大模型企业应用实战(06)-初识LangChain