题解 P5911 【[POI2004]PRZ】

· · 题解

\large{\texttt{P5911}}

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

Update 2020/11/1:

\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}}}