LA 4794 - Sharing Chocolate dp

题意

　　有一块\(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");

     }

 }