[状压DP][枚举子集] UVALive 4794 Sharing Chocolate

题目链接

简单分析易知如果Yes的话整块巧克力一定是从最初的一大块不断地分成矩形来实现的，而一个矩形分成两个小矩形的方法只有两种，横着分或者竖着分，这样的话就可以枚举断点分割，大问题转化为小问题递归解决。然后总共的小块数量最多15，很明显可以用二进制表示获得的块的状态。但是直接定义类似\[dp(r,c,S)\]这样的状态会造成\[O((x+y)xy2^n)\]的复杂度，基本上不能通过这个题（其实做了极致的优化的话时间上应该可以做到但是空间复杂度会超过2GB）。然后考虑状态的进一步化简，可以发现实际上如果确定了S，则可以通过r和c中的一个计算出另一个（或者发现根本不存在这样的数），由此只需要考虑\[dp(r,S)\]即可，其中r是原状态r，c中较小的那一个。另外，枚举分割点时间是并不优秀，因为还得检查当前集合是否支持这样的分割，不如直接枚举所有的子集分割情况，然后用这个来算出分割后的子函数的r和c。按照计算矩阵链乘的方式来做复杂度分析可以算出时间复杂度\[O(x3^n)\]。直接记忆化搜索的话，会比这个上限要小得多。

总体来说是比较简单的一个题，但是因为一开始没有考虑到进一步化简状态而是直接莽，tle了几次。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int maxn = 1e4 + 5;
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;

char vis[105][(1<<16)+5],clk;
bool dp[105][(1<<16)+5];
int a[20],x,y,n;
int val[(1<<16)+5];

void pre(){
    int res;
    for(int i=0;i<(1<<n);i++){
        val[i]=0;
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                val[i]+=a[j+1];
            }
        }
    }
}

bool dps(int r,int c,int S){
    if(r>c) swap(r,c);
    if(vis[r][S]==clk) return dp[r][S]; 
    vis[r][S]=clk;

    if(val[S]!=r*c) return dp[r][S]=0;
    if(__builtin_popcount(S)==1) return dp[r][S]=1;
    int tt;
    for(int S0=S,S1;S0;S0=(S0-1)&S){
        S1=S^S0,tt=val[S0]/r;
        if(tt*r==val[S0]&&dps(r,tt,S0)&&dps(r,c-tt,S1)){
            return dp[r][S]=1;
        }
        tt=val[S0]/c;
        if(tt*c==val[S0]&&dps(tt,c,S0)&&dps(r-tt,c,S1)){
            return dp[r][S]=1;
        }

    }
    return dp[r][S]=0;
}

int main()
{
    while(~scanf("%d",&n)&&n){
        scanf("%d%d",&x,&y);
        clk++;
        int res=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);res+=a[i];
        }
        if(res!=x*y){
            printf("Case %d: ",clk);
            puts("No");
            continue;
        }
        pre();
        printf("Case %d: ",clk);
        if(dps(x,y,(1<<n)-1)) puts("Yes");
        else puts("No");
    }
    return 0;
}