2018 CCPC 秦皇岛 I (状压DP)-白红宇

2018 CCPC 秦皇岛 I (状压DP)

阅读量：4612 次

发布时间：2019-06-09

本文共 1004 字，大约阅读时间需要 3 分钟。

题意：

首先t组数据（t<=5），一个n代表有n件东西，每个东西可以代表两个物品，商品或者袋子，每个都有个值，如果这个要代表袋子的话，当前就代表是容量，而且必须把其他几件不是袋子的物品放一些进来，容量必须正好装满，问你有多少种合法的方案，袋子中放入的物品不同也代表不同，同一件物品只能放入一个袋子

（n<=15）

Sample Input

1 1 1

1 1 2 2 3

1 2 3 4 5 6 7 8 9 10

Sample Output

127

思路：首先我们看数据范围我们就能想到是状压DP，但是我们不能直接去0 1代表哪些是背包物品，这样我们就不确定物品怎么放入背包，所以我们预处理，我们预处理出所有状态是否可以是一个已经放满的背包，并且枚举状态中哪一个才是背包，为了方便计算

weight[i] 代表该状态下所有物品的值的和

f[i] 代表该状态下可以是一个放满的背包的种数

dp[i] 代表该状态下合法的所有种数

我们可以利用weight 计算出 f[i],即我们枚举到当前位时，我们假设当前位是背包 weight[i]-a[i]==a[i] 如果是的话 f[i]++, 因为当前背包容量是a[i]，其他总和也是a[i]，即代表当前背包装满了

然后我们可以利用所有的单个装满的背包合并起来算出最后状态

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #define PI acos(-1.0)#define E 1e-6#define MOD 16007#define INF 0x3f3f3f3f#define N 16#define LL long longusing namespace std;int a[N];int f[1<

转载于:https://www.cnblogs.com/Lis-/p/11587438.html

你可能感兴趣的文章