每日一题 [SCOI2007]压缩 (区间dp)

一.题意

字符串最长50，求压缩后的最短长度。

二.题解

考虑 维护字符串 s[l....r] 可压缩成的最短长度， 第三维维护是否存在 M 。

首先是没有 M 的时候 :

有 M 的时候：

还要考虑满足条件时可以创造出M:

最后的答案就是

三.代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define eps 1e-10
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e5+5;
const int N=5e2+5;
const int mod=1e9+7;

string s;
ll dp[60][60][2];

bool pd(ll l,ll r){
    ll mid = l + r >> 1, len = mid - l + 1;
    return s.substr(l, len) == s.substr(1 + mid, len);
}

int main(){
    io;
    cin>> s; ll n=s.size();  s=" "+s;
    for(int len = 1; len <= n; len++){
        for(int l = 1; l + len - 1 <= n; l++){
            int r = l + len - 1;
            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], 1 +
                min(dp[l][k][1],dp[l][k][0]) + 
                min(dp[k+1][r][1],dp[k+1][r][0])
                );
            }
            if(len % 2 == 0 && pd(l, r))
                dp[l][r][0] = min(dp[l][r][0], dp[l][l + r >> 1][0]+1);
        }
    }
    cout<<min(dp[1][n][0],dp[1][n][1]);
    return 0;
}