rqnoj-275-FOLDING-记忆化搜索

本文主要是介绍rqnoj-275-FOLDING-记忆化搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

记忆化搜索很简单，就是用的时候老是想不到~~无奈的感觉~~~

dp[l][r] :l到r这一段中的最小表示方法。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<string>
#include<stdlib.h>
#define INT_MAX 0x7fffffff
#define maxn 101
#define max3(a,b,c) (max(a,b)>c?max(a,b):c)
#define min3(a,b,c) (min(a,b)<c?min(a,b):c)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
string str;
string dp[maxn][maxn];
string s,ss;
string ns(int x)
{ss="";if(x>=100)ss.push_back(x/100+'0');if(x>=10)ss.push_back((x/10)%10+'0');if(x>0)ss.push_back(x%10+'0');return ss;
}
int pan(int l,int r,int x)
{for(int i=l+x;i<=r;i++){if(str[i]!=str[i-x])return 0;}return 1;
}
string dfs(int l,int r)
{int t;int i;if(dp[l][r]!="")return dp[l][r];if(l==r){dp[l][r].push_back(str[l]);return dp[l][r];}s="";for(i=l;i<=r;i++){dp[l][r].push_back(str[i]);}int len=dp[l][r].size();int fn;for(i=1;i<=len/2;i++){if((r-l+1)%i)continue;if(!pan(l,r,i))continue;t=(r-l+1)/i;fn=1;if(t>9)fn=2;if(t>99)fn=3;s=dfs(l,l+i-1);if(s.size()+2+fn<dp[l][r].size()){dp[l][r]=ns(t)+"("+s+")";}}for(i=l;i<r;i++){if(dfs(l,i).size()+dfs(i+1,r).size()<dp[l][r].size()){dp[l][r]=dp[l][i]+dp[i+1][r];}}return dp[l][r];
}
int main()
{while(cin>>str){for(int i=0;i<101;i++){for(int j=0;j<101;j++)dp[i][j]="";}cout<<dfs(0,str.size()-1)<<endl;}return 0;
}

这篇关于rqnoj-275-FOLDING-记忆化搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---