NC20252（[SCOI2007]压缩 ）

感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100;
int dp[maxn][maxn][2];///dp[l][r][1]表示区间[l,r]中有M(插在pos后面)
int n;
char s[maxn];
void init(){
    for(int i = 1; i <= n; i++){
        dp[i][i][0] = 1; dp[i][i][1] = 2;
    }
}
bool check(int l, int mid, int r){
    for(int i = l, j = mid + 1; j <= r; i++, j++){
        if(s[i] != s[j]) return false;
    }
    return true;
}
int main(){
    scanf("%s", s + 1);
    n = strlen(s + 1);
    init();
    for(int len = 2; len <= n; len++){
        for(int l = 1, r; ; l++){
            r = l + len - 1; if(r > n) break;
            for(int mid = l; mid < r; mid++){
                if(!dp[l][r][0]) dp[l][r][0] = dp[l][mid][0] + r - mid;
                dp[l][r][0] = min(dp[l][r][0], dp[l][mid][0] + r - mid);
                if((r - mid) * 2 == len && check(l, mid, r)){
                    if(!dp[l][r][0]) dp[l][r][0] = dp[l][mid][0] + 1;
                    dp[l][r][0] = min(dp[l][r][0], dp[l][mid][0] + 1);
                }
                if(!dp[l][r][1]) dp[l][r][1] = min(dp[l][mid][0], dp[l][mid][1]) + 1 + min(dp[mid + 1][r][0], dp[mid + 1][r][1]);
                dp[l][r][1] = min(dp[l][r][1], min(dp[l][mid][0], dp[l][mid][1]) + 1 + min(dp[mid + 1][r][0], dp[mid + 1][r][1]));
            }
        }
    }
    printf("%d\n", min(dp[1][n][0], dp[1][n][1]));
    return 0;
}