题目链接
题目大意：有一块x*y的巧克力,每次可以切一刀,问切若干刀后(不能两块同时切),可不可以切成n块,面积分别是a1,a2…an;的巧克力:
解题报告：
f(r,S) 表示 r行是否能切成 集合S（ai的集合）
f(r,S)=1 当且仅当 f(r,S0)==1 && f(r,S-S0)==1
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;const int maxn = 16;
const int maxy = 110;int n, A[maxn], sum[1<<maxn], dp[maxy][1<<maxn], vis[maxy][1<<maxn];int bitcount(int x) { return x==0 ? 0 : bitcount(x>>1)+(x&1); }int dfs( int x, int S ){if( vis[x][S] ) return dp[x][S];vis[x][S]=1;int& ans=dp[x][S];if( bitcount(S)==1 ) return ans=1;int y=sum[S]/x;for ( int s0=(S-1)&S; s0; s0=(s0-1)&S ){int s1=S^s0;if( sum[s0]%x==0 && dfs( min(x,sum[s0]/x),s0) && dfs( min(x,sum[s1]/x), s1) )return ans=1;if( sum[s0]%y==0 && dfs( min(y,sum[s0]/y),s0) && dfs( min(y,sum[s1]/y), s1) )return ans=1;}return ans=0;
}int main(){int kas=0;while( scanf("%d", &n )==1 && n ){memset(vis,0,sizeof(vis));int x, y;scanf("%d%d", &x, &y );for ( int i=0; i<n; i++ ) scanf("%d", &A[i] );memset(sum,0,sizeof(sum));for ( int S=0; S<(1<<n); S++ )for ( int i=0; i<n; i++ ) if( S&(1<<i) ) sum[S]+=A[i];int All=(1<<n)-1, ans=0;if( sum[All]!=x*y || sum[All]%x!=0 ) ans=0;else ans=dfs( min(x,y), All );printf("Case %d: %s\n", ++kas, ans ? "Yes" : "No" );}return 0;
}