BZOJ2073 [POI2004]PRZ

时间:2017-10-17 17:11:34

标签:状压DP,位运算

Description

一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过. 队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.

Input

第一行两个数: w – 桥能承受的最大重量(100 <= w <= 400) n – 队员总数(1 <= n <= 16). 接下来n 行每行两个数分别表示: t – 该队员过桥所需时间(1 <= t <= 50) w – 该队员的重量(10 <= w <= 100).

Output

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

Sample Input

100 3

24 60

10 40

18 50

Sample Output

42

 

题意:N个物品,每个物品有重量Wi和时间Ti,可以选取一些物品组合购买,Wa+Wb+……<=Wmax,对于这些组合购买的物品,只计算其中最大的Ti,使得购买所有物品Ti的总和最小

 

F[i]表示i状态下最优值,可以先预处理出t[i]w[i],之后枚举i之前的状态j,暴力状压,转移枚举子集,使用了一个小技巧加速,否则会TLE

 

Code

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const LL inf=1844387848,ed=1<<18,maxn=20;
LL W,n,a[maxn],b[maxn],f[ed],t[ed],w[ed];

int main()
{
	W=read(),n=read();
	rep(i,1,n)a[i]=read(),b[i]=read();
	rep(i,1,(1<<n)-1)
		for(int j=0;(1<<j)<=i;j++)
			if(1<<j&i){
				w[i]+=b[j+1];
				t[i]=max(t[i],a[j+1]);
			}//预处理w[i]与t[i]
	f[0]=0;
	rep(i,1,(1<<n)-1){
		if(w[i]<=W)f[i]=t[i];else f[i]=inf;//f[i]初始化
		for(int j=(i-1)&i;j;j=(j-1)&i)//注意!!!这里j使用了小技巧加速,可以快速枚举子集
			if(w[i^j]<=W)f[i]=min(f[i],f[j]+t[i^j]);
	}
    printf("%lld\n",f[(1<<n)-1]);
    return 0;
}

作者:qwerty1125 发表于2017/10/17 19:11:34 原文链接
阅读:18 评论:0 查看评论