题意：是否能经过若干次切割把一块x*y的长方形巧克力分成n块，每块是a1,a2,a3...an小块
st表示{a1,a2,...an}的某个子集。
先预处理出全部sum[st]，各个子集的小块总数
dp[l][st]表示长为l，宽为sum[st]/l的长方形能否被分成子集st.因为面积必须相等才有可能
具体的状态转移看代码
int da[16]; int sum[1<<15]; int init(int n) { int total=(1<<n)-1; for(int st=0;st<=total;st++) { sum[st]=0; int k=st,bit=0; while(k>0) { if(k%2==1) { sum[st]+=da[bit]; } k/=2;bit++; } } return 0; } int dp[110][1<<15]; int check(int st) { int k=0; while(st>0) { k+=st%2; st/=2; } return k==1?1:0; } int f(int l,int st) { if(st==0||check(st)) return dp[l][st]=1; if(dp[l][st]>=0)return dp[l][st]; int &ans=dp[l][st]; ans=0; for(int s=(st-1)&st;s>0;s=(s-1)&st) { if(sum[s]%l==0) { int flag=f(max(sum[s]/l,l),s)&&f(max(sum[st^s]/l,l),st^s); if(flag)return ans=1; } int r=sum[st]/l; if(sum[s]%r==0) { int flag=f(max(sum[s]/r,r),s)&&f(max(sum[s^s]/r,r),st^s); if(flag)return ans=1; } } return ans=0; } int main() { int n; int ca=1; while(scanf("%d",&n)!=EOF&&n) { int x,y; scanf("%d%d",&x,&y); for(int i=0;i<n;i++) scanf("%d",&da[i]); init(n); int k=x*y; int total=(1<<n)-1; if(k!=sum[total]) { printf("Case %d: No ",ca++); continue; } memset(dp,-1,sizeof(dp)); int flag=f(max(x,y),total); printf("Case %d: %s ",ca++,flag?"Yes":"No"); } return 0; }