链接: link.

K - Dishonest Driver

题意：

给定一个长度为 N N N的字符串，现在需要将字符串进行压缩，压缩的规则就是相同的子串的可以缩写，例如 a a a b a a a b aaabaaab aaabaaab 缩写成 ( ( a 3 ) b ) 2 ((a^3)b)^2 ((a3)b)2,现在问给定的字符串能压缩成的最短长度

思路：

区间 d p dp dp
定义 d p ( i , j ) dp(i,j) dp(i,j)为从字符串位置从 i 到 j i到j i到j可以压缩成的最短长度
那么此时 s i , j s_{i,j} si,j​的最短循环节长度为 m l e n mlen mlen,如果 l e n i , j len_{i,j} leni,j​是 m l e n mlen mlen的整数倍，且 l e n i , k len_{i,k} leni,k​也是 m l e n mlen mlen的整数倍的话，那么转移方程就是 d p ( i , j ) = m i n ( d p ( i , j ) , d p ( i , k ) ) dp(i,j)=min(dp(i,j),dp(i,k)) dp(i,j)=min(dp(i,j),dp(i,k))
否则就是把两个字符串合并
d p ( i , j ) = m i n ( d p ( i , j ) , d p ( i , k ) + d p ( k + 1 , j ) ) dp(i,j)=min(dp(i,j),dp(i,k)+dp(k+1,j)) dp(i,j)=min(dp(i,j),dp(i,k)+dp(k+1,j))
而最短循环节的长度就直接每次都跑 k m p kmp kmp求出字符串的对应的 n e x t next next数组，然后最短循环节的长度就是 n − n e x t [ n ] n-next[n] n−next[n]，或者提前跑个二维 k m p kmp kmp，预处理二维的 n e x t next next数组,最终输出 d p ( 1 , n ) dp(1,n) dp(1,n)即可

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 777;
char s[N];
int n;
int dp[N][N];
int get_next(int l, int r) {
    char str[N];
    int Next[N] = {0};
    for (int i = 1; i <= r - l + 1; i++) {
        str[i] = s[i + l - 1];
    }
    int n = r - l + 1;
    for (int i = 2, j = 0; i <= n; i++) {
        while (j && str[i] != str[j + 1]) j = Next[j];
        if (str[i] == str[j + 1]) j++;
        Next[i] = j;
    }
    return n - Next[n];
}

int main() {
    cin >> n;
    cin >> s + 1;
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i <= n; i++) {
        dp[i][i] = 1;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = inf;
            int minlen = get_next(i, j);
            for (int k = i; k <= j; k++) {
                int dex = k - i + 1;
                if (len % minlen == 0 && dex % minlen == 0) {
                    dp[i][j] = min(dp[i][j], dp[i][k]);
                } else {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                }
            }
        }
    }
    cout << dp[1][n] << endl;
}