Menu
Article ACM

HDU 4628 Pieces

NodeKey

NodeKey

• 2 min read

CLS的状压DP系列……
然而实际上也算是一道简单题，但是我并没有立刻写出来。
不知道为什么，每次我尝试这用已知最优状态去推其他状态都是错的……
然而用当前状态之前的状态来推当前状态却是对的。

顺便学习了一个，二进制子集的枚举方法。for ( int sta = state ; sta ; sta = (sta - 1) & state )
学了这么久状压居然连这个都知道真是醉了……

题意：
给你一个字符串，每次只能取走一个回文串，问最少取几次。

思路：
先预处理出所有状态是否为回文串，并使得 这个状态取值为 1 。
枚举每个状态，再枚举它的所有子集。
状态转移方程 为 dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s] )

AC Code

#include <bits/stdc++.h>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 16;
const int inf = 0x3f3f3f3f;

char str[maxn];
int dp[1 << maxn];
int len;

void judge(int sta)
{
    if (dp[sta] != inf)
        return;
    int l = 0, r = len - 1;
    while (l < r) {
        while ((sta & (1 << l)) == 0 && l < len - 1)
            l++;
        while ((sta & (1 << r)) == 0 && r > 0)
            r--;
        if (str[l] != str[r]) {
            dp[sta] = inf + 1;
            return;
        }
        l++, r--;
    }
    dp[sta] = 1;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%s", str);
        len = strlen(str);
        int maxs = (1 << len) - 1;
        fill(dp, 0x3f), dp[0] = 0;
        range(sta, 1, maxs) each(j, len) judge(sta | (1 << j));
        range(sta, 1, maxs)
        {
            for (int s = sta; s; s = (s - 1) & sta)
                dp[sta] = min(dp[sta], dp[sta ^ s] + dp[s]);
        }
        printf("%d\n", dp[maxs]);
    }
    return 0;
}
Share