思路：看到n十分于是考虑状压dp，先预处理出处于状态s的情况下过桥的时间和重量，然后枚举状态转移即可，f[i]=min(f[i],f[j]+time[i^j])(j∈i）（自称会状压dp结果连枚举非空子集都不会的我。。。。。）
顺便普及如何枚举非空子集：for (int j=i;j;j=j&(i-1));j就是i的所有非空子集。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; #define maxn 20 #define maxf 1<<20 int limit,n; int a[maxn],b[maxn]; int t[maxf],w[maxf],dp[maxf]; int main(){ scanf("%d%d",&limit,&n); for (int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); for (int i=1;i<(1<<n);i++) for (int j=0;j<n;j++) if (i&(1<<j)){ t[i]=max(t[i],a[j+1]); w[i]+=b[j+1]; } memset(dp,127,sizeof(dp)),dp[0]=0; for (int i=1;i<(1<<n);i++) for (int j=i;j;j=i&(j-1)) if (w[j]<=limit) dp[i]=min(dp[i],t[j]+dp[i^j]); printf("%d ",dp[(1<<n)-1]); return 0; }