LuoguP5911 PRZ

昵称71011036 2020-08-10

展开全文

题目背景

一只队伍在爬山时碰到了雪崩，他们在逃跑时遇到了一座桥，他们要尽快的过桥。

题目描述

桥已经很旧了, 所以它不能承受太重的东西。任何时候队伍在桥上的人都不能超过一定的限制。所以这只队伍过桥时只能分批过，当一组全部过去时，下一组才能接着过。队伍里每个人过桥都需要特定的时间，

当一批队员过桥时时间应该算走得最慢的那一个，每个人也有特定的重量，我们想知道如何分批过桥能使总时间最少。

输入格式

第一行两个数: WW表示桥能承受的最大重量和nn表示队员总数。

接下来nn行：每行两个数:tt表示该队员过桥所需时间和ww表示该队员的重量。

输出格式

输出一个数表示最少的过桥时间。

样例#1

输入:　　　　　　　　　　输出: 42
100 3
24 60
10 40
18 50

数据范围

对于所有的数据，100≤W≤400,1≤n≤16,1≤t≤50,10≤w≤100100≤W≤400,1≤n≤16,1≤t≤50,10≤w≤100 。

思路：

这道题可以有贪心和状压两种做法，而且贪心的效率比状压更高（但是正确性需要斟酌）。

状压做法

这道题如果使用状压的话，那么这就是一道枚举子集进行转移的题目。

在DP之前，我们还是需要考虑状态设计。这道题目中，我们有33个状态，分别是fw[i]fw[i]表示ii这个集合中所有人的体重之和，ft[i]ft[i]表示ii这个集合中所有人过桥需要的时间，f[i]f[i]表示ii这个集合中所有人过桥需要的最小时间。

显然fw[i]fw[i]和ft[i]ft[i]是作为预处理的数组存在的，fw[i]fw[i]用来判断这些人的体重是否符合要求，ft[i]ft[i]就是用来转移。

对于f[i]f[i]而言，它的转移就是状压DP的经典转移方法————枚举子集。我们每次枚举到一个子集ss，首先判断fw[s]fw[s]是否满足要求，若不满足要求，那么这种情况就不需要转移，直接跳过；若满足要求，那么f[i]=min(f[i],ft[s]+f[i　xor　s])f[i]=min(f[i],ft[s]+f[i　xor　s])。

最后答案即为f[(1<<n−1)]f[(1<<n−1)]

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MAXN 130172
int W, n;
int w[20], t[20];
int fw[MAXN], ft[MAXN];
int f[MAXN];
inline int read(void){
    int f = 1, x = 0;char ch;
    do{ch = getchar();if(ch=='-')f = -1;} while (ch < '0' || ch > '9');
    do{ x = (x << 1) + (x << 3) + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}
inline int _min(int x, int y) { return x < y ? x : y; }
inline int _max(int x, int y) { return x > y ? x : y; }
int main(){
    W = read(), n = read();
    for (int i = 1; i <= n;++i)
        t[i] = read(), w[i] = read();
    for (int i = 0; i < (1 << n);++i){
        for (int j = 1; j <= n;++j){
            if(((i>>(j-1))&1)==0) continue;//若当前枚举到的人不在该集合中，则不需要考虑
            fw[i] += w[j], ft[i] = _max(ft[i], t[j]);//体重直接就是加和，而时间根据题意，是取该组中时间最长的那个
        }
    }
    memset(f, 127, sizeof(f));
    f[0] = 0;//初始化不要忘了
    for (int i = 0; i < (1 << n);++i){//枚举所有的可能
        for (int j = i; j;j = (j - 1) & i){//枚举i的子集
            if(fw[j]>W) continue;//若体重超标，那么就不能进行转移
            f[i] = _min(f[i], ft[j] + f[i ^ j]);//转移时就是相当于上一批是(i^j),这一批是j
        }
    }
    printf("%d\n", f[(1 << n) - 1]);
    return 0;
}

贪心

贪心就没啥可说的了吧，就是让时间代价高的人尽可能去消耗其他时间代价高的人。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
int W, n, ans;
bool flag[20];
class node{
    public:
        int w, t;
} ip[20];
inline int read(void){
    int f = 1, x = 0;char ch;
    do{ch = getchar();if(ch=='-')f = -1;} while (ch < '0' || ch > '9');
    do{ x = (x << 1) + (x << 3) + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}
inline bool cmp(const node x,const node y){
    return x.t > y.t;
}
int main(){
    W = read(), n = read();
    for (int i = 1; i <= n;++i)
        ip[i].t = read(), ip[i].w = read();
    std::sort(ip + 1, ip + n + 1, cmp);//排序（从大到小）
    for (int i = 1; i <= n;++i){
        if(flag[i]) continue;
        int wt = 0;
        for (int j = i; j <= n;++j){
            if(flag[j]||wt+ip[j].w>W) continue;
            flag[j] = 1;
            wt += ip[j].w;
        }
        ans += ip[i].t;//只加当前组中时间代价最大的那个
    }
    printf("%d\n", ans);
    return 0;
}