题目描述
有 \(N\) 个景点,第 \(i\) 个属于公司 \(c_i\)。当你第一次路过一个属于公司 \(i\) 的景点时,你会获得 \(w_i\) 元。
在景点之间有 \(m\) 条单向道路连接 \(u,v(u<v)\)。一开始你在景点 \(1\)。求到所有景点 \(1\le i\le N\) 时最多能获得多少元。
思路
由于公司数量很少,所以考虑状压。
如果直接状压的话很好想到。但这里 \(N\le 36\),似乎只用加一点点优化就行了。
而这里状压是记录哪些公司被访问过了。但我们的目的是为了不重复统计一个公司的贡献。所以只需记录出现次数 \(\ge 2\) 的公司即可。
总共记录的只有 \(\frac{N}{2}=18\),可以接受。
空间复杂度 \(O(2^{\frac{N}{2}} \cdot N)\),时间复杂度 \(O(2^{\frac{N}{2}} \cdot N^2)\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 40, INF = 40000001;
int n, m, c[MAXN], w[MAXN], cnt[MAXN], _id[MAXN], tot, dp[MAXN][1 << 18], g[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= n; ++i) {
cin >> c[i];
cnt[c[i]]++;
}
for(int i = 1; i <= n; ++i) {
cin >> w[i];
if(cnt[i] > 1) {
tot++;
_id[i] = tot - 1;
}
}
for(int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
g[u][v] = 1;
}
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < (1 << tot); ++j) {
dp[i][j] = -INF;
}
}
dp[1][(cnt[c[1]] > 1 ? (1 << _id[c[1]]) : 0)] = w[c[1]];
for(int i = 1; i <= n; ++i) {
int Max = 0;
for(int j = 0; j < (1 << tot); ++j) {
if(dp[i][j] < 0) {
continue;
}
Max = max(Max, dp[i][j]);
for(int v = 1; v <= n; ++v) {
if(g[i][v]) {
dp[v][j | (cnt[c[v]] > 1 ? (1 << _id[c[v]]) : 0)] = max(dp[v][j | (cnt[c[v]] > 1 ? (1 << _id[c[v]]) : 0)], dp[i][j] + (cnt[c[v]] <= 1 || !((j >> _id[c[v]]) & 1) ? w[c[v]] : 0));
}
}
}
cout << Max << "\n";
}
return 0;
}
标签:cnt,int,GYM,状压,tot,103389,MAXN,id
From: https://www.cnblogs.com/yaosicheng124/p/18414383