首页 > 代码库 > LA 4794 Sharing Chocolate

LA 4794 Sharing Chocolate

2024-07-18 10:58:48   223人阅读

大白书中的题感觉一般都比较难，能理解书上代码就已经很不错了

按照经验，一般数据较小的题目，都有可能是用状态压缩来解决的

题意：问一个面积为x×y的巧克力，能否切若干刀，将其切成n块面积为A1，A2，，，An块巧克力。(每次只能沿直线切一块巧克力)

设计状态：

f(r, c, S) = 1表示r行c列的巧克力可以切成面积集合为S的若干块巧克力

分解问题：

f(r, c, S) = 1当且仅当

  1. 横着切：存在1≤r0＜r和S的子集S0，使得f(r0, c, S0) = f(r-r0,c, S-S0) = 1.   或者
  2. 竖着切：存在1≤C0＜C和S的子集S0，使得f(r, C0, S0) = f(r,C-C0, S-S0) = 1.

状态的优化：

因为f(r, c, S) = f(c, r, S)，所以我们去掉一个参数，并且假设r≤c

记f(r, S)表示min(r, sum[S]/r)行max(r, sum[S]/r)列的巧克力能否切成面积和为sum[S]的若干块

 

DP函数中那句 int& ans;的作用是什么作用不太懂，我开始时去掉以后WA掉了，Orz

这句留着以后再弄懂吧，=_=||

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 16; 8 const int maxw = 100 + 10; 9 int a[maxn], sum[1 << maxn], f[1 << maxn][maxw], vis[1 << maxn][maxw];10 11 int bitcount(int S)12 {13     return S == 0 ? 0 : (S & 1) + bitcount(S >> 1);14 }15 16 int dp(int S, int x)17 {18     if(vis[S][x])    return f[S][x];19     vis[S][x] = 1;20     int& ans = f[S][x];21     if(bitcount(S) == 1)22         return ans = 1;23     int y = sum[S] / x;24     for(int S0 = (S-1)&S; S0 != 0; S0 = (S0-1)&S)25     {26         int S1 = S - S0;27         if(sum[S0] % x == 0 && dp(S0, min(x, sum[S0]/x)) && dp(S1, min(x, sum[S1]/x)))28             return ans = 1;29         if(sum[S0] % y == 0 && dp(S0, min(y, sum[S0]/y)) && dp(S1, min(y, sum[S1]/y)))30             return ans = 1;31     }32     return ans = 0;33 }34 35 int main(void)36 {37     #ifdef LOCAL38         freopen("4794in.txt", "r", stdin);39     #endif40 41     int kase = 0, n;42     while(scanf("%d", &n) == 1 && n)43     {44         int x, y;45         scanf("%d%d", &x, &y);46         for(int i = 0; i < n; ++i)47             scanf("%d", &a[i]);48 49         memset(sum, 0, sizeof(sum));50         for(int i = 0; i < (1 << n); ++i)51             for(int j = 0; j < n; ++j)52                 if(i & (1 << j))53                     sum[i] += a[j];54 55         memset(vis, 0, sizeof(vis));56         int All = (1 << n) - 1;57         int ans;58         if(sum[All] != x*y)59             ans = 0;60         else61             ans = dp(All, min(x, y));62         printf("Case %d: %s\n", ++kase, ans ? "Yes" : "No");63     }64     return 0;65 }
代码君

 


联系
我们