网站职位推荐怎么做百度应用商店官网

题意：是否能经过若干次切割把一块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\n",ca++);continue;}memset(dp,-1,sizeof(dp));int flag=f(max(x,y),total);printf("Case %d: %s\n",ca++,flag?"Yes":"No");}return 0;
}