题意
有一块\(x*y\)的巧克力,问能否恰好分成n块,每块个数如下
输入格式
n
x y
a1 a2 a3 ... an
首先\(x \times y 必然要等于 \sum\limits_{i=1}^{n}a_i\)
设集合状态为S,则转移方程为
\(f(x,y,S)=(f(x,c_0,S_0)\&\& f(x,y-c_0,S_1))\|(f(c_0,y,S_0)\&\& f(x-c_0,y,S_1)) \) 分别对应横着掰和竖着掰
由于 \(x \times y = \sum\limits_{i=1}^{n}a_i\) 故可以简化为f(x,S) x为min(x,y)
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int org[];
int sum[<<],Max;
int f[][<<],vis[][<<];
int count_one(int x) //统计1的个数
{
x=(x&0x55555555)+(x>>&0x55555555);
x=(x&0x33333333)+(x>>&0x33333333);
x=(x&0x0F0F0F0F)+(x>>&0x0F0F0F0F);
x=(x&0x00FF00FF)+(x>>&0x00FF00FF);
x=(x&0x0000FFFF)+(x>>&0x0000FFFF);
return x;
}
int dp(int x,int S)
{
if(vis[x][S])return f[x][S]; //记忆化搜索
vis[x][S]=;
int &ans=f[x][S],S1,y=sum[S]/x;
ans=;
if(count_one(S)==)return ans=;
for(int S0=(S-)&S;S0;S0=(S0-)&S)
{
S1=S-S0;
if(sum[S0]%x==&&dp(min(x,sum[S0]/x),S0)&&dp(min(x,sum[S1]/x),S1)) //横着掰
return ans=;
if(sum[S0]%y==&&dp(min(y,sum[S0]/y),S0)&&dp(min(y,sum[S1]/y),S1)) //竖着掰
return ans=;
}
return ans;
}
int main()
{
int n,i;
int x,y,C=;
while(~scanf("%d",&n)&&n)
{
scanf("%d%d",&x,&y);
for(i=;i<n;i++)
scanf("%d",&org[i]);
memset(vis,,sizeof(vis));
Max=(<<n)-;
int S;
for(S=;S<=Max;S++)//记录每一个状态对应的巧克力块和
{
sum[S]=;
for(i=;i<n;i++)
if(S&(<<i))sum[S]+=org[i];
}
int ans=;
if(sum[Max]==x*y)ans=dp(min(x,y),Max);
printf("Case %d: %s\n",++C,ans?"Yes":"No");
}
}