赛时犯唐没预处理T和W导致复杂度过高挂了10分

$1≤N≤16$+最少时间 显然状压dp

$f[i]$ 指状态 $i$ 时的最少时间

$f[i] = min_j(f[i\oplus j] + T[j](W[j] <= m))$

upd:枚举子集方法

for(int s = st;;s = (s - 1) & st){
	if(!s) break;
}

code:

#include <bits/stdc++.h>
using namespace std;

const long long N = 18;

long long m, n, t[N], w[N];

void read(){
	cin >> m >> n;
	for(long long i = 1;i <= n; i++){
		cin >> t[i] >> w[i];
	}
	return ;
}

long long f[1<<N], T[1<<N], W[1<<N];

void compute(){
	for(long long i = 1;i < (1<<n); i++){
		for(int j = 1;j <= n; j++){
			if((i>>(j-1))&1){
				W[i] += w[j];
				T[i] = max(T[i],t[j]);
			}
		}
	}
	for(long long i = 1;i < (1<<n); i++){
		f[i] = INT_MAX;
		for(long long j = i;;j = (j-1) & i){
			if(W[j] <= m){
				f[i] = min(f[i],T[j] + f[i^j]);
			}
			if(j == 0) break;
		}
	}
	cout << f[(1<<n)-1];
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	read();
	compute();
	return 0;
}

状压好题~

1≤N≤16，这是在疯狂暗示用状压啊！

那就用呗

设dp[i]表示合法情况下，状态为i时，最少用的时间。

转移

枚举（从哪种状态转移过来的）除去本次过河的人（i^j），剩余过河人（j）的状态，判断是否合法（W[i^j]<=m），取个min就好啦

预处理

k = (1<<n)-1;
for (ll i=1; i<=n; i++)
	cin>>t[i]>>w[i];
for (ll i=0; i<=k; i++) {
	for (ll j=1; j<=n; j++) {
		if (i&(1<<(j-1))) {
			T[i] = max(T[i], t[j]);
			W[i] += w[j];
		}
	}
}

状压

memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (ll i=0; i<=k; i++) {
	for (ll j=i; ; j=i&(j-1)) {
		if (W[i^j]<=m) dp[i] = min(dp[i], dp[j]+T[i^j]);
		if (!j) break;
	}
}

完结散花~QwQ