http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2631

状态:dp[i] 表示 s[0...i] 的最小划分数
转移:dp[i] = min{dp[j] | j<i 且 s[j+1...i] 是回文串}
判断回文串可以用 Manacher 预处理后做到 O(1) 判断,这样转移就是 O(n) 复杂度了。

/* 0.039s */
const int mx = int(1e3) + 5;

char ss[mx], s[mx << 1]; /// ss为源串
int n, len[mx << 1], dp[mx];

void init()
{
    mem(s, 0), s[0] = '$';
    int i;
    for (i = 0; ss[i]; ++i) s[(i << 1) + 1] = '#', s[(i + 1) << 1] = ss[i];
    n = i;
    s[(i + 1) << 1] = '#';
    mem(len, 0);
    int right = 0, mid = 0;
    for (i = 1; s[i]; ++i)
    {
        len[i] = (i < right ? min(len[(mid << 1) - i], right - i) : 1);
        while (s[i + len[i]] == s[i - len[i]]) ++len[i];
        if (right < i + len[i]) mid = i, right = i + len[i];
    }
}

inline bool Q(int l, int r) /// 判断ss[l...r]是否为回文串
{
    return len[l + r + 2] >= r - l + 1;
}

int solve()
{
    int i, j;
    For(i, n)
    {
        dp[i] = (Q(0, i) ? 1 : i + 1);
        if (dp[i] > 1) For(j, i) if (Q(j + 1, i)) Qmin(dp[i], dp[j] + 1);
    }
    return dp[n - 1];
}

int main()
{
    int t;
    SI(t);
    while (t--)
    {
        SS(ss);
        init();
        PI(solve());
    }
    return 0;
}

Comments

comments powered by Disqus