题目链接
题目
折叠的定义如下:- 一个字符串可以看成它自身的折叠。记作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。
思路
区间dp
首先必然枚举中间点,然后左右合并。
也可以枚举循环节,然后暴力判断。
判断之前先看一下是否为长度的因数,如果暴力后是否能使答案更小,然后就不会被卡。
原则上时间复杂度 \(O(n^4)\),然后必然卡不满,相当于 \(O(n^3)\) 加个小常数,最坏也就 \(O(n^3\sqrt n)\)。
tips:与UVA1351双倍经验哦!
Code
// Problem: UVA1351 String Compression
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA1351
// Memory Limit: 0 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 210
int n, m, i, j, k;
int f[N][N];
char s[N];
int l, r, len, t;
int length(int x)
{
int ans=0;
while(x) ++ans, x/=10;
return ans;
}
int pan(int l, int r, int k)
{
for(i=l+k; i<=r; ++i)
if(s[i]!=s[i-k]) return 0;
return 1;
}
int check(int l, int r, int k)
{
if(2+f[l][l+k-1]+length(len/k)>=f[l][r]) return 999;
if(pan(l, r, k)) return 2+f[l][l+k-1]+length(len/k);
return 999;
}
signed main()
{
// freopen("tiaoshi.in", "r", stdin);
// freopen("tiaoshi.out", "w", stdout);
// t=read();
t=1;
while(t--)
{
scanf("%s", s+1);
n=strlen(s+1);
for(i=1; i<=n; ++i) f[i][i]=1;
for(len=2; len<=n; ++len)
for(l=1, r=l+len-1; r<=n; ++l, ++r)
{
f[l][r]=len;
for(k=l; k<r; ++k) f[l][r]=min(f[l][r], f[l][k]+f[k+1][r]);
for(k=1; k*k<=len; ++k)
if(len%k==0)
{
f[l][r]=min(f[l][r], check(l, r, k));
f[l][r]=min(f[l][r], check(l, r, len/k));
}
}
printf("%d\n", f[1][n]);
}
return 0;
}