UVA 1630 记忆化搜索

2019-11-06 08:38:02

字体：大中小

来源：转载

供稿：网友

题意

输入一个字符串，折叠成一个尽量短的串。问最短可以折叠成什么样子的一个串。

题解

设dp[i][j]为字符串i到j折叠成最短的字符串后的长度，ss[i][j]为字符串i到j折叠成的最短的字符串。DFS+记忆化搜索即可。

注意事项

输入的字符串右边界为str.size()-1，需要特别注意。

代码

#include <iostream>#include<cstdio>#include<algorithm>#include<cstring>#define INF 1e9using namespace std;int dp[110][110];string ss[110][110];string str;int judge(int l,int r){ for(int i=1;i<=(r-l+1)/2;i++){ if((r-l+1)%i!=0) continue; bool re=true; for(int j=l;j+i<=r;j++){ if(str[j]!=str[j+i]){ re=false; break; } } if(re) return i; } return 0;}int dfs(int l,int r){ if(dp[l][r]!=-1) return dp[l][r]; if(l==r){ dp[l][r]=1; ss[l][r]=str[l]; return 1; } int ans=INF; int k=0; for(int i=l;i<r;i++){ int len=dfs(l,i)+dfs(i+1,r); if(len<ans){ ans=len; k=i; } } ss[l][r]=ss[l][k]+ss[k+1][r]; dp[l][r]=ans; int le=judge(l,r); if(le){ bool can=true; for(int i=l;i<=r;i++){ if(str[i]=='('||str[i]==')') can=false; } int nu=(r-l+1)/le; char ch[20]; sPRintf(ch,"%d",nu); string newstr=ch+string("(")+ss[l][l+le-1]+string(")"); if(can&&newstr.size()<dp[l][r]){ ss[l][r]=newstr; dp[l][r]=newstr.size(); } } return dp[l][r];}int main(){ while(cin>>str){ int r=str.size()-1; memset(dp,-1,sizeof(dp)); dfs(0,r); cout<<ss[0][r]<<endl; } return 0;}

上一篇：每日练习(4)

下一篇：团体程序设计天梯赛L2-016 愿天下有情人都是失散多年的兄妹