SGU 475 状压 DP

题意

传送门 SGU 475 Be a Smart Raftsman

题解

容易想到枚举每一条路上使用船的人员集合，时间复杂度 O ( 2 2 n m ) O(2^{2n}m) O(22nm)。考虑如何优化状态转移的过程。对于任一个状态， 其转移都可以通过改变每一个人的位置得到，对应于二进制压缩的状态即每一位的异或。那么可以将已改变位置状态的人数作为 DP 的阶段（类似于 Floyd 求最短路的想法）， O ( 2 n n ) O(2^nn) O(2nn) 完成状态转移。

总时间复杂度 O ( m n 2 n ) O(mn2^n) O(mn2n)。

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 11, MAXM = 1E3 + 5, INF = 0x3f3f3f3f;
int N, M;
int W[MAXN], T[MAXN], S[MAXN];
int C[MAXM], D[MAXM], D2[MAXM];
int sw[1 << MAXN], mx[1 << MAXN];
int dp[1 << MAXN];void _min(int &x, int y) { x = min(x, y); }int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> N >> M;for (int i = 0; i < N; ++i)cin >> W[i] >> T[i] >> S[i];for (int i = 0; i < M; ++i)cin >> C[i] >> D[i] >> D2[i];for (int i = 0; i < 1 << N; ++i)for (int j = 0; j < N; ++j)if (i >> j & 1)sw[i] += W[j], mx[i] = max(mx[i], T[j]);memset(dp, 0x3f, sizeof(dp));dp[0] = 0;int mask = (1 << N) - 1;for (int i = 0; i <= M; ++i){if (i > 0)dp[0] = INF;for (int k = 0; k < N; ++k)for (int j = 0; j < 1 << N; ++j)_min(dp[j ^ 1 << k], dp[j] + S[k]);if (i == M)break;for (int j = 1; j < 1 << N; ++j)dp[j] += max((sw[j] > C[i] ? D[i] : D2[i]), mx[~j & mask]);}cout << dp[0] << '\n';return 0;
}