NC20252 [SCOI2007]压缩(区间DP)

题目链接

题意：




题解：

最后答案取dp[1][n][0/1]的最小值即可

AC代码

/*
    Author : zzugzx
    Lang : C++
    Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9+7;
//const int mod = 998244353;
const double eps = 1e-10;
const double pi = acos(-1.0);
const int maxn = 1e6+10;
const ll inf = 0x3f3f3f3f;
const int dir[][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

string s;
int dp[100][100][2];
bool ok(int l, int r) {
    int mid = l + r >> 1;
    for (int i = l; i <= mid; i++)
        if (s[i] != s[i + mid - l + 1])
            return false;
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
//  freopen("in.txt", "r", stdin);
//  freopen("out.txt", "w", stdout);
    cin >> s;
    int n = s.length();
    s = '.' + s;
    for (int len = 1; len <= n; len++)
        for (int l = 1, r = l + len - 1; r <= n; l++, r++){
            dp[l][r][0] = dp[l][r][1] = len;
            for (int k = l; k < r; k++){
                dp[l][r][0] = min(dp[l][r][0], dp[l][k][0] + r - k);
                dp[l][r][1] = min(dp[l][r][1], min(dp[l][k][1], dp[l][k][0]) + 1 + min(dp[k + 1][r][0], dp[k + 1][r][1]));
            }
            if (len % 2 == 0 && ok(l, r))
                dp[l][r][0] = min(dp[l][r][0], dp[l][(l + r) / 2][0] + 1);
        }
    cout << min(dp[1][n][1], dp[1][n][0]);
    return 0;
}