「Bzoj 1090」「SCOI2003」字符串折叠 (区间DP)

发表于 | 分类于 | | + s

Bzoj 1090
这题和Bzoj 1068差不多，但是简单一些，1068的一个M对应很多R，而1090括号一一对应，使得这题的转移变得非常简单了。
设$f(i,j)$为$[i,j]$折叠后的长度(包括括号的长度)
考虑枚举中间点，$f(i,j)=min(f(i,k)+f(k+1,j))$
而只压缩前后的情况，由于括号一一对应，所以这些情况都在上面的情况之中了，不同于1068
而整个区间压缩，$f(i,j)=min(f(i,i+k-1)+cal(len/k)$，其中$len=j-i+1$.当且仅当$[i,j]$为长为$k$的子串循环而来，$cal(k)$用来计算括号的长度
边界值：$f(i,i)=1$，所有$f(i,j)$初始化为$j-i+1$
然后就可以DP了，同样记忆化搜索好写一些，用记忆化，不用考虑枚举顺序

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 100 + 5;
char s[MAXN];
int n, f[MAXN][MAXN];
int cal(int x) {//返回括号占位 
    if (x == 1) return 0;
    if (x < 10) return 1 + 2;
    if (x < 100) return 2 + 2;
    return 3 + 2;
}
bool check(int i, int j, int k) {//是否是长为k的子串循环而来 
    int len = j - i + 1;
    if (len % k != 0 || i + k - 1 > n) return false;
    for (int a = 1; a < len / k; a++) {
        for (int b = 1; b <= k; b++) {
            if (s[i + b - 1] != s[i + b + a * k - 1]) return false;
        }
    }
    return true;
}
int dp(int i, int j) {
    int len = j - i + 1, tmp = len;
    if (f[i][j] >= 0) return f[i][j];
    if (len == 1) return f[i][j] = 1;
    for (int k = i; k < j; k++) tmp = min(tmp, dp(i, k) + dp(k + 1, j));
    for (int k = 1; k <= len / 2; k++) if (check(i, j, k)) tmp = min(tmp, dp(i, i + k - 1) + cal(len / k));
    return f[i][j] = tmp;
}
void clean() {
    ms(f, -1);
}
void solve() {
    clean();
    n = strlen(s + 1);
    printf("%d\n", dp(1, n));
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%s", s + 1), solve();
    return 0;
}
------ 本文结束 ------