BZOJ 2073: [POI2004]PRZ – [状压DP]


题目传送门(BZOJ)
>原文链接<

题解 :

状态 :F[S]代表状态为S下花的最少时间

首先预处理出来每个状态需要花的时间及重量。

对于要更新的状态i枚举其子集,若这个i对这个子集的补集重量小于限定的重量,就用它来更新i

答案是F[(1<<n)-1]

代码 :

#include 
#include 
#include 
using namespace std;
const int N = 16;
int W, n, m;
int wei[1<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注