Educational Codeforces Round 25 F. String Compression(kmp+dp)
程序员文章站
2024-03-14 14:25:28
...
题解:这个题无非就是想找到字符串每一段的循环节。经典KMP便可以找到字符串的循环节。问题解决
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
char s1[8010],s2[8010];
int len;
int Next[8010];
void get_next(int len2)
{
Next[0]=-1;
int i=0,j=-1;
while(i<len2)
{
if(j==-1||s2[i]==s2[j])
{
i++,j++;
Next[i]=j;
}
else
j=Next[j];
}
}
int p(int x)
{
int ans=0;
while(x)
{
ans++;
x/=10;
}
return ans;
}
int dp[8010];
int main()
{
scanf("%s",s1);int len=strlen(s1);
for(int i=1;i<=len;i++)dp[i]=i+1;
for(int i=0;i<len;i++)
{
strcpy(s2,s1+i);
get_next(len-i);
for(int j=1;j+i<=len;j++)
{
int l=j-Next[j];
if(j%l==0)
dp[i+j]=min(dp[i+j],dp[i]+l+p(j/l));
else
dp[i+j]=min(dp[i+j],dp[i]+1+j);
}
}
printf("%d\n",dp[len]);
return 0;
}
上一篇: 对称加密算法之Java AES算法应用
下一篇: DES加解密