LA4794 Sharing Chocolate

题目

LA4794 Sharing Chocolate

题解

看到数据范围就是状压嘛，，本来觉得复杂度x*3^n太高了会炸结果就是那样。然后发现自己忽略了很多状态是不合法的不会被转移到，所以推荐使用记忆化搜索。然后注意一下，还是输出的时候，特判了之后要么return要么另外输出的时候加else 一个else没看到花了20min，简直了。

代码

//QWsin #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=15; const int maxm=100+5; int dp[(1<<maxn)+10][maxm],area[maxn+10]; int Area[(1<<maxn)+10];//集合中选中的对应面积和 int kase=0; inline void print(const char *s){printf("Case %d: %s\n",++kase,s);} int n; int f(int S,int a)//集合，长边 { if(dp[S][a]!=-1) return dp[S][a]; if(Area[S]%a) return 0; int &ans=dp[S][a],b=Area[S]/a; if(a<b) swap(a,b);//由于下方转移时有点事情所以这里要换一下 if(dp[S][a]!=-1) return dp[S][a]; for(int S0=(S-1)&S;S0;S0=(S0-1)&S) { if(f(S0,a)&&f(S^S0,a)) return ans=1;//跟上面呼应，a不一定是长边 if(f(S0,b)&&f(S^S0,b)) return ans=1; } return ans=0; } inline void solve() { memset(dp,-1,sizeof dp); int X,Y,sum=0;scanf("%d%d",&X,&Y); for(int i=0;i<n;++i) { scanf("%d",area+i);sum+=area[i]; int sz=sqrt(area[i]); for(int j=1;j<=sz;++j) if(area[i]%j==0) dp[1<<i][area[i]/j]=1;//先把单个长边处理出来 } for(int S=0;S<(1<<n);++S) { Area[S]=0; for(int i=0;i<n;++i) if(S & (1<<i)) Area[S]+=area[i]; } if(X*Y!=sum) print("No"); else print(f((1<<n)-1,X)?"Yes":"No"); } int main() { while(scanf("%d",&n)==1&&n) solve(); return 0; }