bzoj1090 SCOI2003 字符串折叠（区间dp

题目描述

折叠的定义如下：

一个字符串可以看成它自身的折叠。记作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

输出 #1

14

说明/提示

一个最短的折叠为：2(NEERC3(YES))

分析

一个区间的最短长度由两种情况得来。
①：由两个子区间合并而来
②：由某个循环节构成
于是我们用 $f\left[i\right]\left[j\right]$f[i][j] 表示区间 $[i,j]$[i,j] 的最短长度， $t$t 表示 循环节长度， $s1\left[i\right]$s1[i] 表示循环节个数的位数

于是得到转移方程
$f\left[i\right]\left[j\right]=min\left(f\right[i\left]\right[j],f[i\left]\right[k]+f[k+1\left]\right[j\left]\right)k\in [i,j)$f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])  k∈[i,j)
$if\left(check\right(i,j,t\left)\right)f\left[i\right]\left[j\right]=min\left(f\right[i\left]\right[j],s1[l/t]+2+f[i\left]\right[i+t-1\left]\right)$if(check(i,j,t))   f[i][j]=min(f[i][j],s1[l/t]+2+f[i][i+t−1])

我是来说说复杂度的

咋一看复杂度是 $O\left(n^4\right)$O(n4) ，其实不然。
我们记 $\tau \left(i\right)$τ(i) 为 $i$i 的约数个数
那么复杂度是 $O(n^2\ast {\sum }_{i=1}^n\tau (i\left)\right)$O(n2∗i=1∑n​τ(i))
求 ${\sum }_{i=1}^n\tau \left(i\right)$i=1∑n​τ(i)，转化为考虑 $i$i 作为约数对答案的贡献，也就是 $i$i 的倍数
这样的话， ${\sum }_{i=1}^n\tau \left(i\right)={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor \&lt;{\sum }_{i=1}^n\frac{n}{i}\&lt;nlnn\&lt;nlogn$i=1∑n​τ(i)=i=1∑n​⌊in​⌋<i=1∑n​in​<nlnn<nlogn
后面那个是调和级数，为啥是这样，因为 $\frac{1}{i}$i1​ 的原函数是 $lni$ln i。
因此复杂度是 $O\left(n^{3}logn\right)$O(n3logn)

代码如下

#include <bits/stdc++.h>
using namespace std;
int s1[104], f[104][104];
char s[105];
int check(int l, int r, int len){
	for(int i = l; i <= r; i++){
		if(i + len <= r && s[i] != s[i + len]) return 0;
	}
	return 1;
}
int main(){
	int i, j, n, m, k, t, l;
	for(i = 2; i <= 9; i++) s1[i] = 1;
	for(i = 10; i <= 99; i++) s1[i] = 2;
	s1[100] = 3;
	scanf("%s", s);
	n = strlen(s);
	memset(f, 1, sizeof(f));
	for(i = 0; i < n; i++) f[i][i] = 1;
	for(i = n - 1; i >= 0; i--){
		for(j = i + 1; j < n; j++){
			l = j - i + 1;
			for(k = i; k < j; k++) f[i][j] = min(f[i][j], f[i][k] + f[k+1][j]);
			for(k = i; k < j; k++){
				t = k - i + 1;
				if(l % t != 0) continue;
				if(check(i, j, t)) f[i][j] = min(f[i][j], s1[l / t] + 2 + f[i][k]);
			}
		}
	}
	printf("%d", f[0][n-1]);
	return 0;
}