【World Finals】2010 J

【试题编号】
2010 J
【名称】
Sharing Chocolate
【题目大意】
给n*m的方格 每次可以沿平行x或y切一刀 问最后能不能分成指定的一些面积
【算法讨论】
f[i][j] 表示长为i的方格 j值状压变量 表示这里面有哪些面积 对应的宽可以求出来
每次枚举一个切的方法 然后枚举j的切分 进行更新 用记忆话比较好做
【时空复杂度】
O(n^2 * 2^k * 2^k)
O(n*2^k)
【code】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
int n, x, y, a[20], sum[40000];
bool f[105][40000], b[105][40000];
int lowbit(int a)
{
    return a & (-a);
}
bool dfs(int x, int y, int t)
{
    if (b[x][t]) return f[x][t];
    if (!(t - lowbit(t)))
        return b[x][t] = f[x][t] = true;
    bool br = false;
    for (int i = 1; i < x; ++i)
    {
        if (br) break;
        for (int j = (t - 1) & t; j; j = (j - 1) & t)
            if (i * y == sum[j] && (x - i) * y == sum[t ^ j] && dfs(i, y, j) && dfs(x - i, y, t ^ j))
            {
                br = true;
                break;
            }
    }
    for (int i = 1; i < y; ++i)
    {
        if (br) break;
        for (int j = (t - 1) & t; j; j = (j - 1) & t)
            if (x * i == sum[j] && x * (y - i) == sum[t ^ j] && dfs(x, i, j) && dfs(x, y - i, t ^ j))
            {
                br = true;
                break;
            }
    }
    b[x][t] = true;
    return f[x][t] = br;
}
int main()
{
    int test = 0;
    while (scanf("%d", &n) && n)
    {
        scanf("%d%d", &x, &y);
        memset(f, 0, sizeof(f));
        memset(b, 0, sizeof(b));
        memset(sum, 0, sizeof(sum));
        for (int i = 0; i < n; ++i)
            scanf("%d", &a[i]);
        for (int i = 0; i < (1 << n); ++i)
            for (int j = 0; j < n; ++j)
                if (i & (1 << j))
                    sum[i] += a[j];
        printf((dfs(x, y, (1 << n) - 1) ? "Case %d: Yes\n" : "Case %d: No\n"), ++test);
    }
}

发表评论