BZOJ1090: [SCOI2003]字符串折叠（区间dp）

本文主要是介绍BZOJ1090: [SCOI2003]字符串折叠（区间dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
折叠的定义如下： 1. 一个字符串可以看成它自身的折叠。记作S  S 2. X(S)是X(X>1)个S连接在一起的串的折叠。记作X(S)  SSSS…S(X个S)。 3. 如果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。

Input
仅一行，即字符串S，长度保证不超过100。

Output
仅一行，即最短的折叠长度。

Sample Input
NEERCYESYESYESNEERCYESYESYES
Sample Output
14
HINT
一个最短的折叠为：2(NEERC3(YES))

Source

思路：
区间dp，选定区间的时候，判断是否有重复子区间，有的话就可以转移。

ACNEW

#include <ctime>
#include <iostream>
#include <assert.h>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>using namespace std;typedef long long ll;char s[105];
int f[105][105],num[105];void init() {num[0] = 0;for(int i = 1;i <= 100;i++) {num[i] = num[i / 10] + 1;}
}bool check(int sta,int k,int l) {for(int i = 0;i < l;i++) {if(s[i + sta] != s[i % k + sta]) return false;}return true;
}int main() {init();scanf("%s",s + 1);int n = strlen(s + 1);for(int i = 1;i <= n;i++) {f[i][i] = 1;}for(int l = 2;l <= n;l++) { //长度for(int i = 1;i + l - 1 <= n;i++) { //起点int j = i + l - 1; //终点f[i][j] = l;for(int k = i;k < j;k++) {f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j]);}for(int k = i;k < j;k++) {if(l % (k - i + 1) != 0) continue;if(check(i,k - i + 1,l)) {f[i][j] = min(f[i][j],f[i][k] + num[l / (k - i + 1)] + 2);}}}}printf("%d\n",f[1][n]);return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int f[1005][1005];
char s[10005];int solve(int x)
{if(x < 10)return 1;else if(x >= 10 && x <= 99)return 2;return 3;
}bool check(int l,int mid,int r)
{int x = l;for(int i = mid + 1;i <= r;i++){if(s[i] != s[x])return false;x++;if(x == mid + 1)x = l;}return true;
}int main()
{scanf("%s",s + 1);int n = (int)strlen(s + 1);for(int l = 1;l <= n;l++){for(int i = 1;i + l - 1 <= n;i++){int j = i + l - 1;f[i][j] = j - i + 1;for(int k = i;k < j;k++){f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j]);}for(int k = i;k < j;k++){int len = k - i + 1;if(l % len != 0)continue;if(check(i,k,j))f[i][j] = min(f[i][j],f[i][k] + 2 + solve(l / len));}}}printf("%d\n",f[1][n]);return 0;
}