题解 UVA1099 【Sharing Chocolate】

Stinger · 2020-10-18 10:26:00 · 题解

这道题一看 n\leq 15，状压DP无疑了……

我们可以设出一个显而易见的状态：f[x][y][s] 表示在 x\times y 的矩形中分成 s 中的每一块巧克力是否可行。

这样空间显然会炸，我们可以发现，f 数组中保存了太多的无用状态——有了 x 和 s，y 就可以唯一确定了。这样只需要用 f[x][s] 表示在一条边长为 x 的矩形中分成 s 中的每一块巧克力是否可行即可。这样数组大小缩到了3276800，还是bool数组，稳过。

为了方便计算矩形的另一条边长，我们可以预处理出 Sum[s] 数组表示 S 中的巧克力的总面积。

方程很好列了，枚举子集 s0 再判断是否能整除即可。详见代码。

另外希望大家不要忘了register与inline的重要性！论怎样不开O2卡进最优解。

Code:

#include <cstdio>
#include <cstring>
#include <cassert>
#define min(x, y) (x < y ? x : y)

int Sum[1 << 15], A[16], n, x, y, sum;
bool f[105][1 << 15], Visit[105][1 << 15], flag[1 << 15];

inline bool scan() {
    sum = 0;
    scanf("%d", &n);
    if (n == 0) return false;
    scanf("%d%d", &x, &y);
    for (register int i(1); i <= n; ++ i) scanf("%d", A + i), sum += A[i]; 
    memset(f, false, sizeof(f));
    memset(flag, false, sizeof(flag));
    memset(Visit, false, sizeof(Visit));
    memset(Sum, 0, sizeof(Sum));
    for (register int s(1); s < 1 << n; ++ s)
    for (register int i(0); i < n; ++ i) if (s & 1 << i) Sum[s] += A[i + 1];
    for (register int i(0); i < n; ++ i) flag[1 << i] = true;
    return true;
}

inline bool dfs(int x, int s) {
    if (Visit[x][s]) return f[x][s];
    if (Visit[Sum[s] / x][s]) return f[Sum[s] / x][s];//能让搜索量减半的东西，不用每次取min，这里加一行就好了。
    Visit[x][s] = true;
    if (flag[s]) return f[x][s] = true;
    register int y(Sum[s] / x);
    for (register int s0(s - 1 & s); s0; s0 = s0 - 1 & s) {
        if (!(Sum[s0] % x) && dfs(x, s0) && dfs(x, s ^ s0)) return f[x][s] = true;
        if (!(Sum[s0] % y) && dfs(y, s0) && dfs(y, s ^ s0)) return f[x][s] = true;
    }
    return f[x][s];
}

int main() {
    int kase(0);
    while (scan())
        printf("Case %d: ", ++ kase),
        puts(!(sum % x) && sum == x * y && dfs(x, (1 << n) - 1) ? "Yes" : "No");
}