这道题目的DP思想挺先进的，用状态DP来表示各个子巧克力块。原本是要 dp(S,x,y)，S代表状态，x,y为边长，由于y可以用面积/x表示出来，就压缩到了只有两个变量，在转移过程也是很巧妙，枚举S的子集s0,然后 s1=S-s0来代表除该子集的另一个集合，接下来分两种情况，如果这个子集是通过把 S保留x，切割y，则转移到dp(s0,x)和dp(s1,x)，另一种情况是转移到dp(s0,y)和dp（s1,y）。为了更加缩小状态，统一把转移方程的 x换成 min(x,sum[S]/x)，sum为该状态下的面积
#include <cstdio> #include <cstring> #include <algorithm> //#include <cmath> #define N 1<<17 using namespace std; int f[N][120],sum[N]; int A[20],vis[N][120]; int ok(int x) //测试当前状态下是否只剩下一种巧克力，是的话，二进制状态里必定只有一个1，因此只会返回1 否则则返回其他值. { if (x==0) return 0; return ok(x/2)+(x&1);//这里导致我WA了好几次，原因是没注意&的优先级低，要括号起来 } int dp(int S,int x) { if (vis[S][x]) return f[S][x]; vis[S][x]=1; //int& ans=f[S][x]; if (ok(S)==1) return f[S][x]=1; //如果满足，则说明以及到达某块具体巧克力的状态，完成任务 return 1回去 int y=sum[S]/x; for (int s0=S&(S-1);s0;s0=S&(s0-1))//枚举S的子集 { int s1=S-s0; if (sum[s0]%x==0 && dp(s0,min(x,sum[s0]/x)) && dp(s1,min(x,sum[s1]/x))) return f[S][x]=1;//这里分两种情况，分别代表两个子集的产生 是切割y 或者 切割x产生的 if (sum[s0]%y==0 && dp(s0,min(y,sum[s0]/y))&& dp(s1,min(y,sum[s1]/y))) return f[S][x]=1; } return f[S][x]=0; } int main() { int kase=0,n,x,y; while (scanf("%d",&n)!=EOF) { if (n==0) break; scanf("%d%d",&x,&y); for (int i=0;i<n;i++) scanf("%d",&A[i]); memset(sum,0,sizeof sum); for (int i=0;i<(1<<n);i++) { for (int j=0;j<n;j++) { if (i&(1<<j)) { sum[i]+=A[j]; } } } memset(vis,0,sizeof vis); int all=(1<<n)-1; int ans=0; if (sum[all]!=x*y || sum[all]%x!=0) { ans=0; } else { ans=dp(all,min(x,y)); } printf("Case %d: %s ",++kase,ans==1? "Yes":"No"); } return 0; }