时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
折叠的定义如下：
一个字符串可以看成它自身的折叠。记作S = S X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S) = SSSS…S(X个S)。
如果A = A’, B = B’，则AB = A’B’ 例如，因为3(A) = AAA, 2(B) = BB，所以3(A)C2(B) =
AAACBB，而2(3(A)C)2(B) = AAACAAACBB给一个字符串，求它的最短折叠。例如AAAAAAAAAABABABCCD的最短折叠为：9(A)3(AB)CCD。
输入描述:
仅一行，即字符串S，长度保证不超过100。
输出描述:
仅一行，即最短的折叠长度。
示例1
输入
复制
NEERCYESYESYESNEERCYESYESYES
输出
复制
14
题解：
菜。。。我太菜了
dp[l][r]表示l~r的最短折叠长度
dp[l][r]=min(r-l+1,dp[l][k]+dp[k+1][r]) l<=k<r
当区间[k+1,r]可以由区间[l,k]重复时，dp[l][r]=min(dp[l][r],dp[l][k]+2+calc((r-l+1)/(k-l+1))
2是指 括号 占的位数
calc是指系数所占位数
最终答案是dp[0][len-1]
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=140;
int dp[maxn][maxn];
bool vis[maxn][maxn];
char s[maxn];
bool check(int l,int r,int cl,int cr)
{
if((r-l+1)%(cr-cl+1)!=0)return false;
for(int i=l;i<=r;i++)
{
if(s[i]!=s[(i-l)%(cr-cl+1)+cl])return false;
}
return true;
}
int calc(int x)//x是几位数
{
int ans=0;
while(x)
{
x/=10;
ans++;
}
return ans;
}
int dfs(int l,int r)
{
if(l==r)return 1;
if(vis[l][r])return dp[l][r];
vis[l][r]=true;
dp[l][r]=r-l+1;
for(int i=l;i<r;i++)
{
dp[l][r]=min(dp[l][r],dfs(l,i)+dfs(i+1,r));
if(check(i+1,r,l,i))
{
dp[l][r]=min(dp[l][r],dfs(l,i)+2+calc((r-i)/(i-l+1)+1));
}
}
return dp[l][r];
}
int main()
{
//cin>>s;
scanf("%s",s);
int sum=dfs(0,strlen(s)-1);
cout<<sum;
}
京公网安备 11010502036488号