CF825F String Compression

CF, DP, KMP

　　题意：把一个字符串压缩成CiSi格式（例：hhhhhhh压缩为7h），问压缩后最短长度是多少。 - 原题链接

　　DP思路很显然，我们使用f[i]表示压缩字符串前i位的最短长度，辅助数组g[i][j]表示压缩s[i, j]的最短长度。

　　这道题最大的收获是学到关于sprintf的用法，将数字i写进足够大的char数组buf中，返回buf的长度：


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=8000+10;
int n, nx[maxn], c[maxn], f[maxn], g[maxn][maxn];
char s[maxn], buf[maxn];
void KMP(char *ch, int len)
{
	nx[1]=0;
	for(int i=2, j=0; i<=len; i++)
	{
		while(j && ch[i]!=ch[j+1])	j=nx[j];
		if(ch[i]==ch[j+1])	++j;
		nx[i]=j;
	}
	return ;
}
int main()
{
	while(scanf("%s", s+1)!=EOF)
	{
		n=strlen(s+1);
		memset(g, 0, sizeof g);
		for(int i=1; i<=n; i++)
		{
			c[i]=sprintf(buf, "%d", i);
			f[i]=i+1;	//每个字符串T都能压缩为1T
		}
		for(int i=1; i<=n; i++)
		{
			KMP(s+i-1, n-i+1);	//传进去的是s+i-1，保证函数中合法字符串从下标1开始计数
			for(int j=1; j<=n-i+1; j++)
			{
				int len=j-nx[j];
				if(j%len==0)	g[i][i+j-1]=c[j/len]+len;	//循环次数+循环节长度
				else g[i][i+j-1]=1+j;	//不循环
			}
		}
		for(int i=1; i<=n; i++)
			for(int j=0; j<i; j++)
				f[i]=min(f[i], f[j]+g[j+1][i]);
		
		printf("%d\n", f[n]);
	}
	return 0;
}