Uva(1099)(sharingchocolatlie)

链接：https://vjudge.net/problem/UVA-1099
思路：10年wf的题，还是首先来建立状态。遍历当前集合，如果里面有一个面积的蛋糕是当前长或者宽的因子，那么就可以切，然后把该元素从集合中剔除，进入到下一个状态。我们考虑到最多分15个蛋糕，那么子集有2的15次方-1个，32767个，然后长和宽各为100，一共327670000个状态，很明显要超时超内存。考虑一下，当i确定的时候，就已经明确了集合中还有哪几个元素，此时总面积也是确定的，所以我们可以预处理算出集合中有某些元素时的面积，此时为了压缩状态，我们取长和宽中小的那一个标记状态，另一个可以由面积/该边得出。这样以来复杂度降低了很多，就可以通过了（这种方法确实牛逼啊，膜拜老刘）
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,x,y,o=0;
int a[16];
int dp[66000][101],nsum[66000];
int vis[66000][101];

int bitcount(int x){//计算是否只剩一个元素
    return x==0?0:bitcount(x/2)+(x&1);
}

int dfs(int i,int j){
    if(vis[i][j])return dp[i][j];
    vis[i][j] = 1;
    int& ans = dp[i][j];
    if(bitcount(i)==1)//如果只剩一个元素，则返回真
return ans = 1;
    int y = nsum[i]/j;//算出另一边
    for(int s=(i-1)&i;s;s=(s-1)&i){//枚举所有子集的方法
        int s1 = i-s;//子集与全集对应的差集
        if(nsum[s]%j==0&&dfs(s,min(j,nsum[s]/j))&&dfs(s1,min(j,nsum[s1]/j)))//为长的因子且切开的两部分都有解，则当前状态有解
            return  ans = 1;
        if(nsum[s]%y==0&&dfs(s,min(y,nsum[s]/y))&&dfs(s1,min(y,nsum[s1]/y)))//为宽的因子且切开的两部分都有解，则当前状态有解
            return ans = 1;
    }
    return ans = 0;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d",&n)&&n){
        scanf("%d%d",&x,&y);
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
         }
         for(int i=0;i<(1<<n);i++){
            nsum[i] = 0;
            for(int j=0;j<n;j++){
                if(i&(1<<j))nsum[i]+=a[j];
            }
         }
         memset(vis,0,sizeof(vis));
         int all = (1<<n)-1;
         int ans;
         if(nsum[all]!=x*y||nsum[all]%x!=0)ans = 0;
         else ans = dfs(all,min(x,y));
         printf("Case %d: %s\n",++o,ans?"Yes":"No");
       }
    return 0;
}