LA 4794 Sharing Chocolate（状压DP）

左手的ㄟ右手 2021-12-14 04:25 182阅读 0赞

## 题意：给出一个长宽确定的矩形，每次可以沿一条直线把它分割成两块长宽都为整数的矩形，问能否通过多次操作得到n块面积分别为a1,a2...an的矩形。 ##

## 分析：《训练指南》P75。 ##

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn = 16;
    const int maxw = 100 + 10;
    int n, A[maxn], sum[1<<maxn], f[1<<maxn][maxw], vis[1<<maxn][maxw];
    
    int bitcount(int x) { return x == 0 ? 0 : bitcount(x/2) + (x&1); }
    
    int dp(int S, int x) {
      if(vis[S][x]) return f[S][x];
      vis[S][x] = 1;
      int& ans = f[S][x];
      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&&dp(S0,min(x,sum[S0]/x))&&dp(S1,min(x,sum[S1]/x))) return ans = 1;
        if(sum[S0]%y==0&&dp(S0,min(y,sum[S0]/y))&&dp(S1,min(y,sum[S1]/y))) return ans = 1;
      }
      return ans = 0;
    }
    
    int main() {
      int kase = 0, n, x, y;
      while(scanf("%d", &n) == 1 && n) {
        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];
    
        memset(vis, 0, sizeof(vis));
        int ALL = (1<<n) - 1;
        int ans;
        if(sum[ALL] != x*y || sum[ALL] % x != 0) ans = 0;
        else ans = dp(ALL, min(x,y));
        printf("Case %d: %s\n", ++kase, ans ? "Yes" : "No");
      }
      return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关【状压DP】Most Powerful

[E-Most Powerful\_牛客竞赛动态规划专题班状压dp例题 (nowcoder.com)][E-Most Powerful_dp_ _nowcoder.com]

以你之姓@/ 2024年03月17日 08:58/ 0 赞/ 74 阅读

相关【状压DP】简单环

怎么办，感觉现在所谓会的算法都是云的以为自己会，然后随便出一道题就不会云玩家是吧好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好烦好

柔情只为你懂/ 2024年03月17日 08:57/ 0 赞/ 59 阅读

相关 group 状压dp

　　应某些人要求，我把标签删掉了　　这是一道好题。　　一看$c<=16$果断状压，但是怎么压？　　一个很显然的思路是，枚举上下两层的状态，每一层的状态极限有$C（c

逃离我推掉我的手/ 2023年08月17日 16:48/ 0 赞/ 140 阅读

相关 Woj 1608 - Calculation 状压dp

思路来自于武大的一个大神并不是我的。。。题目链接：[http://acm.whu.edu.cn/land/problem/detail?problem\_id=1608&

柔情只为你懂/ 2022年08月21日 14:59/ 0 赞/ 199 阅读

相关 HDU3182-状压dp

Hamburger Magi Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K

川长思鸟来/ 2022年07月13日 14:56/ 0 赞/ 223 阅读

相关 HDU4114-floyd+ 状压dp

Disney's FastPass Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/327

柔光的暖阳◎/ 2022年07月11日 13:40/ 0 赞/ 234 阅读

相关状压dp（瞎BB）

最近在写状压dp，写得不太顺利啊，抠很久才抠出来。可见如此之菜。状态压缩dp（简称状压dp）是一种非常典型的动态规划，通常使用在NP问题的小规模求解中，虽然是指数

迷南。/ 2022年06月17日 08:13/ 0 赞/ 245 阅读

相关方格取数（状压DP）

include<cstdio> include<iostream> include<algorithm> using namespace std

系统管理员/ 2022年05月28日 07:55/ 0 赞/ 237 阅读

相关 LA 4794 Sharing Chocolate（状压DP）

题意：给出一个长宽确定的矩形，每次可以沿一条直线把它分割成两块长宽都为整数的矩形，问能否通过多次操作得到n块面积分别为a1,a2...an的矩形。分析：《训练指南》P

左手的ㄟ右手/ 2021年12月14日 04:25/ 0 赞/ 183 阅读

相关 Problem Arrangement (状压DP)

Problem Arrangement [ZOJ - 3777 ][ZOJ - 3777] The 11th Zhejiang Provincial Collegiat

た入场券/ 2021年12月13日 01:35/ 0 赞/ 311 阅读