自动搬运

查看原文

来自洛谷，原作者为

	RedreamMer 一拍桌子，两眼放光，三十分钟，四百分贝，五指指天，六重积分，七次反演，八维凸包，九只 log，十种做法，全部假啦！！！

搬运于2025-08-24 22:15:33，当前版本为作者最后更新于2020-06-14 12:32:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\large{\texttt{P5911}}$

题目标签：状压 $\texttt{DP}$

Update 2020/11/1:

• 感谢

  https://www.luogu.com.cn/user/238875
  yu__xuan](https://www.luogu.com.cn/user/142110) 指出状压代码中的错误

• 感谢

  https://www.luogu.com.cn/user/123294
  了贪心做法的错误

$\large{\texttt{Solution}}$

1. 贪心

此方法有误，数据也加强了，现在代码过不去

题目中各个数据都比较小，但是注意到 $n \le 16$ ，很明显出题人是想让我们用状压 $\texttt{DP}$ 来做这道题。我就不用

显然题目中说了，必须要让每一个人都过桥，并且每次过桥的时间为最慢的那个人的时间，因此所有人中越慢的人对答案的贡献就越大，为了避免这些大贡献的人贡献时间，那么我们就可以用贪心的套路，让那些最慢的人在一起过桥，最快的人一起过桥，这样可以让时间最小化。

这种思路是错的，感谢Alex_Wei的hack数据：

Input:

10 4
20 8
15 9
10 1
5 2

Answer:
35

2. 状压DP

首先，$dp[i]$ 为状态为 $i$ 下，这些队员过桥最少要用的时间，再维护一下每个状态 $i$ 的总重量 $W$ 以及总时间 $T$ （指一次过桥的重量和时间，不管这个状态能否过桥）。

接着，顺序枚举状态 $i$ ，并枚举 $j$ ($j \in i$ )，将 $i$ 分为状态 $j$ 和状态 $i \oplus j$ ，意思就是 状态 $j$ 的一次过桥时间 $+$ 状态 $i$ 的最优过桥时间，注意状态 $j$ 的总重量要小于题目给定的 $w$ ，更新 $dp[i]$

$$dp[i] = \min (dp[i],T[j]+dp[i \oplus j] )(W[j] \le w) $$

$\large{\texttt{Code}}$

状压DP

1950 ms

#include<bits/stdc++.h>
using namespace std;

//#define int long long
//#define PB push_back
const int N=16;
//const int M=110;

int a,b,t[N],w[N],T[1<<N],W[1<<N],dp[1<<N];


signed main() {
	scanf("%d%d",&a,&b);
	const int mx=(1<<b)-1;
	for(int i=1;i<=b;i++) scanf("%d%d",&t[i],&w[i]);
	for(int i=0;i<=mx;i++) {
		for(int j=1;j<=b;j++) {
			if(i&(1<<(j-1))) {
				T[i]=max(T[i],t[j]);//预处理出状态i的T和W
				W[i]+=w[j];
			}
		}
	}
	memset(dp,0x3f,sizeof dp);
	dp[0]=0;//初始化dp
	for(int i=0;i<=mx;i++) {
		for(int j=i;;j=i&(j-1)) {//这样就可以枚举完i的所有属于它的状态j，原理就不再多说了
			if(W[i^j]<=a) dp[i]=min(dp[i],dp[j]+T[i^j]);
			if(!j) break;
		}
	}
	printf("%d",dp[mx]);//dp[max]即为所求
	return 0;
}

$\blue{\large{\texttt{My Blog}}}$