[DP记忆化 字符串] UVa1630 Folding

[DP记忆化 字符串] UVa1630 Folding

DP[i][j]。i，j分别表示起始位置，终止位置，数组存该段压缩后的长度。一个串的最短压缩可以有两种情况：1.其本身是重复的，压缩其本身达到最短。2.将其分为两段，两段压缩后连接达到最短。

#includeusing namespace std;const int INF= 0x3f3f3f3f;string str;int DP[110][110];string fold[110][110];int judge(int l,int r){ //judge repeat //这里判重用的就是枚举 for(int i=1;i<=(r-l+1)/2;i++) { if((r-l+1)%i) continue; bool flag=true; for(int j=l;j+i<=r;j++) { if(str[j]!=str[j+i]) { flag=false; break; } } if(flag) return i; } return false;}int fun(int l,int r){ if(DP[l][r]!=-1) return DP[l][r]; if(l==r){ DP[l][r]=1; fold[l][r]=str[l]; return 1; } int k; int re=INF; for(int i=l;i>str){ int R=str.size()-1; memset(DP,-1,sizeof(DP)); fun(0,R); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。