题目地址：http://vjudge.net/problem/UVALive-4794
为什么刘汝佳的思路永远天经地义的对，而我的就是错错错，不，是没有思路
这道题问题难在怎么定义状态：
我靠，那么多奇形怪状的巧克力，长宽任意的，怎么表示啊！
那就别想怎么表示一个r*c的巧克力的，反正也办不到
换个思路，想想怎么切，一整块只能横着切或者竖着切，比如说r*c的，可以变成r*(c-c0)和r*c0或者c*r0和c*(r-r0),也就是新生成的每一块的长或宽至少有一个和之前的一样，
并且，切出来的长方形可以任意组合的，比如要切出两块4的和2的巧克力，你不用管它怎么组合，怎么拼在一起的，它肯定是由一块6的巧克力切出来的
所以可以用递推： 假设S，S0表示要切出来的几块巧克力大小，（ r*c，S）的巧克力，能切成（(r-r0)*c,S0）和（r0*c，S-S0） 其中S0是S的子集，这是指横着切，还可以竖着切，与横着切一样。递归边界是，S中只有一块，那么肯定是行的
剩下就是优化了：
因为S表示该r*c巧克力要切出来几块巧克力大小（S是集合表示的），那么S的和sum[S]也就是S中所有巧克力大小的和要等于r*c，那么非法的状态可以全部剪枝掉
因为r*c的和c*r的巧克力等价，所以以r<=c来定义状态
貌似这种切一刀，再切一刀，分一块在分一块都是递推
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=16,maxw=100+5;
int A[maxn],sum[1<<maxn],f[1<<maxn][maxw];
int bitCount(int x){return x?bitCount(x>>1)+(x&1):0;}
int DP(int S,int r){ //r<=cint& ans=f[S][r];if(ans!=-1) return ans;if(bitCount(S)==1) return ans=1; //只剩下一块了且肯定是合法的操作，肯定是可以的int c=sum[S]/r;for(int S0=(S-1)&S;S0;S0=(S0-1)&S0) { //枚举S的子集和S0int S1=S-S0; //将S的一大块巧克力分解为S0和S1这两块//因为只能横着切或者竖着切，那么分解后的一边肯定是r或cif(sum[S0]%r==0&&DP(S0,min(r,sum[S0]/r))&&DP(S1,min(r,sum[S1]/r))) return ans=1;if(sum[S0]%c==0&&DP(S0,min(c,sum[S0]/c))&&DP(S1,min(c,sum[S1]/c))) return ans=1;}return ans=0;
}
int main(int argc, char const *argv[])
{int n,kase=0;while(scanf("%d",&n)==1&&n){int r,c; scanf("%d%d",&r,&c);REP(i,0,n-1) scanf("%d",&A[i]);memset(sum,0,sizeof(sum));REP(S,0,(1<<n)-1) REP(i,0,n-1) //预处理sum[],sum[S]表示S分块方案中总共巧克力有几块if(S&(1<<i)) sum[S]+=A[i];int ALL=(1<<n)-1;bool ok; memset(f,-1,sizeof(f));if(sum[ALL]!=r*c) ok=false;else ok=DP(ALL,min(r,c));printf("Case %d: %s\n", ++kase,ok?"Yes":"No");}return 0;
}