作者：用户wuhqqnrd0m | 来源：互联网 | 2024-11-04 17:38
本文由编程笔记#小编为大家整理，主要介绍了Be a Smart Raftsman SGU475相关的知识，希望对你有一定的参考价值。 传送门题目大意有m+1个点，0是起点，m是终点，i-1到i有一条边
本文由编程笔记#小编为大家整理，主要介绍了Be a Smart Raftsman SGU475相关的知识，希望对你有一定的参考价值。
传送门
题目大意
有m+1个点，0是起点，m是终点，i-1到i有一条边，有一个船由0驶往m，不能返回，它在载重小于等于ci时通过第i条边消耗的时间为di否则为Di，现在有n个人，每个人体重为wi，上船或下船消耗时间为si，如果自己走则通过每一条边消耗的实际均为ti，要求船上必须一直有人，求所有人到终点消耗的时间。
分析
首先我们不难想到状压dp，使得msk记录每个人是否在船上，所以不难想到用dp[i][msk]表示走过i条边现在在船上的人是msk所需要的最短时间，发现我们状态需枚举i和msk，复杂度m*2n，转移需要枚举新msk，复杂度2n，所以总复杂度为O(m*22n)，显然是不行的，所以我们考虑优化。我们发现对于每一个人的上下船关系是独立的，与其他人无关，所以我们可以考虑每次对于一个状态只改变一个人的状态（即只让一个人上船或下船），之后在通过改变的新状态更新下一个状态，这样便可以在数次更新之后得到和之前相同的结果，我们发现这是的转移复杂度便降到了n，所以最终的复杂度变为O(nm*2n)。
代码
#include<iostream>
#include
#include
#include<string>
#include
#include
#include
#include
#include
#include
#include
#include<set>
#include;
for(i=1;i<=n;i++)
scanf("%d%d%d",&w[i],&t[i],&s[i]);
for(i=1;i<=m;i++)
scanf("%d%d%d",&c[i],&D[i],&d[i]);
memset(M,0,sizeof(M));
memset(T,0,sizeof(T));
for(i=0;i<=all;i++)
for(j=0;j)
if(i&(1<<j)){
M[i]+=w[j+1];
}else T[i]=max(T[i],t[j+1]);
memset(dp,0x3f,sizeof(dp));
dp[0][0]=0;
for(i=0;i)
for(j=0;j<=all;j++)
dp[0][j^(1<0][j^(1<0][j]+s[i+1]);
for(i=1;i<=m;i++){
dp[i][0]=0x3f3f3f3f;
for(j=1;j<=all;j++)
if(dp[i-1][j]<0x3f3f3f3f)
if(M[j]>c[i])dp[i][j]=dp[i-1][j]+max(D[i],T[j]);
else dp[i][j]=dp[i-1][j]+max(d[i],T[j]);
for(j=0;j)
for(k=0;k<=all;k++)
dp[i][k^(1<1<1]);
}
printf("%d
",dp[m][0]);
return 0;
}
京公网安备 11010802041100号