[文章目录]
Description
一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过. 队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少. w – 桥能承受的最大重量(100 <= w <= 400) 和 n – 队员总数(1 <= n <= 16)
状压DP
dp[s]表示s这个状态走完所需的最小时间。预处理每个可以一次走完的状态的时间。转移的时候枚举子集。时间复杂度O(3^n)
自己写的dfs很菜啊，看人家的枚举子集方式，orz
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,t[20],w[20];
int dp[1<<17],W,T,root;
void dfs(int s,int now)
{
if(s==0){dp[root]=min(dp[root],dp[root^now]+dp[now]); return ;}
dfs(s-(-s&s),now);
dfs(s-(-s&s),now|(-s&s));
}
void dfs1(int step,int x)
{
if(W>m) return ;
if(step>n){dp[x]=T; return ;}
dfs1(step+1,x);
int tmp=T; T=max(T,t[step]); W+=w[step];
dfs1(step+1,x|(1<<(step-1)));
T=tmp; W-=w[step];
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;++i) scanf("%d%d",t+i,w+i);
memset(dp,0x3f,sizeof dp); dfs1(1,0);
for(int s=1;s<(1<<n);++s) root=s,dfs(s,0);
//神奇枚举子集的方法，学习了一个：for(int j=s;j;j=s&(j-1)) j s^j即为两个子集
printf("%d",dp[(1<<n)-1]);
return 0;
}