题意：能否把一块面积为x*y的巧克力分成面积分别为a1, a2, a3, ..., an的小块巧克力。
题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2795
——>>集合上的动态规划～～好喜欢～～设d[S][x]为把面积为x^y的矩形分成S集合中的各个矩形的能与否。
状态转移：
用行（列，最小的那个）分割时：
如果存在 sum[S0] % x == 0 && dp(S0, min(x, sum[S0]/x)) && dp(S1, min(x, sum[S1]/x));
或者
用列（行，最小的那个）分割时：
如果存在 sum[S0] % y == 0 && dp(S0, min(y, sum[S0]/y)) && dp(S1, min(y, sum[S1]/y));
d[S][x]就能成功分割。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;const int maxn = 15 + 1;
const int maxs = 100 + 10;
int sum[1<<maxn];
bool vis[1<<maxn][maxs], d[1<<maxn][maxs];int bitcount(int S) //统计集合S的元素个数
{return !S ? 0 : bitcount(S/2) + (S&1);
}
bool dp(int S, int x)
{if(vis[S][x]) return d[S][x];vis[S][x] = 1;bool& ans = d[S][x];if(bitcount(S) == 1) return ans = 1; //边界，集合S只有自己一个元素，不用再拆分int y = sum[S] / x;for(int S0 = (S-1)&S; S0; S0 = S & (S0-1)) //枚举S的所有子集{int S1 = S^S0;if((sum[S0] % x == 0 && dp(S0, min(x, sum[S0]/x)) && dp(S1, min(x, sum[S1]/x)))|| (sum[S0] % y == 0 && dp(S0, min(y, sum[S0]/y)) && dp(S1, min(y, sum[S1]/y))))return ans = 1;}return ans = 0;
}int main()
{int n, x, y, a[16], cnt = 1, i, S;while(scanf("%d", &n) == 1 && n){scanf("%d%d", &x, &y);for(i = 0; i < n; i++) scanf("%d", &a[i]);for(S = 0; S < (1<<n); S++) //统计各子集面积{sum[S] = 0;for(i = 0; i < n; i++)if(S & (1<<i))sum[S] += a[i];}int ALL = (1<<n) - 1;memset(vis, 0, sizeof(vis));if(sum[ALL] != x*y || !dp(ALL, min(x, y)))printf("Case %d: No\n", cnt++);elseprintf("Case %d: Yes\n", cnt++);}return 0;
}