codeforces 825F (简单dp + KMP)

题意：

给出一个字符串，你要把它尽量压缩成一个短的字符串，比如一个字符串ababab你可以转化成3ab，长度为 3，比如bbbacacb转化成3b2ac1b，长度为 7，aaaaaaaaaa转化为10a，长度为 3。

思路：先n^2预处理出i,j之间的需要多少长度变成，然后简单状态转移一下。预处理的时候要运用到next数组的性质，即求一个字符串的最小循环的长度，如果len % (len - next[len]) ！= 0那么最小长度为len，否则为 len / (len - next[len]).所以预处理的时候枚举每个字符串的起点，然后得到next数组。

PS：本来以为8000 * 8000不行，没想到过了

#include<iostream>
#include<cstdio>
#include<cstring>


using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define clr(x,y) memset(x,y,sizeof x)
#define PI acos(-1.0)
#define ITER set<int>::iterator
const int Mod = 1e9 + 7;

const int maxn = 8000 + 10;
char s[maxn];

int nextval[maxn];

void get_next(char *T)
{
    int len = strlen(T);
    int j, k;
    j = 0; k = -1; nextval[0] = -1;
    while(j < len)
        if(k == -1 || T[j] == T[k])
            nextval[++j] = ++k;
        else
            k = nextval[k];

}
int dp[maxn];
int a[maxn][maxn];
int fun(int x){int ret = 0;while(x)x /= 10,ret ++;return ret;}
void Init()
{
    int len = strlen(s);
    for(int i = 0;i < len;i ++)
    {
        get_next(s + i);
        for(int j = i;j < len;j ++)
        {
            if(j == i){a[i][j] = 2;continue;}

            int t1 = j - i + 1,t2 = t1 - nextval[t1];
            a[i][j] = t1 % t2 == 0 ? t2 + fun(t1/t2) : t1 + 1;
        }
    }
//    for(int i = 0; i < len;i ++)
//    {
//        for(int j = i; j < len;j ++)
//            cout << i << " " << " " << j << " " << a[i][j] << endl;
//    }
}
void solve()
{
    int len = strlen(s);dp[0] = 2;
    for(int i = 1; i < len;i ++)
    {
        dp[i] = a[0][i];
        for(int j = 0; j < i; j ++)dp[i] = min(dp[i],dp[j] + a[j + 1][i]);
//        cout << i << " " << dp[i] <<endl;
    }
    printf("%d\n",dp[len - 1]);
}
int main()
{
    while( ~ scanf("%s",s))
    {
        Init();
        solve();
    }
    return 0;
}