题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<bits/stdc++.h>
using namespace std;
int main() {
int n, y;
cin >> n >> y;
vector<int> a(n + 5);
vector<int> p(n + 5);
vector<int> head;
for(int i = 1;i <= n;i ++) {
cin >> a[i];
if(a[i] != 0) {
p[a[i]] = i;
}
else head.push_back(i);
}
vector<int> v;
int smart;
for(auto x : head) {
int cnt = 0;
while(x) {
++ cnt;
if(x == y) {
smart = cnt;
break;
}
x = p[x];
}
if(!x) v.push_back(cnt);
}
bitset<1005> dp;
dp.set(smart);
for(auto x : v) {
dp |= dp << x;
}
for(int i = 1;i <= n;i ++) {
if(dp[i]) cout << i << endl;
}
return 0;
}
|
bitset优化01背包
dp 存储能表示的数，dp << x相当于在原来的所有能表示的数上再加上 x，dp |= dp << x则表示原来能表示的数和加上 x 后能表示的所有数。
dp.set(smart) 即对 smart 位设为1， 设为 0 则为 reset。