一道入门必做的题目
思路
里面的关系是一个树状的无环图，每个节点我们显然有两种取法，参加派对，不参加派对，所以状态转移方程就出来了
- 参加派对 (dp[i][1] = dp[i][1] + dp[i_{son}][0])，上司参加了舞会，其直系下属不能参加舞会
- 不参加派对 (dp[i][0] = dp[i][0] + max(dp[i_{son}][1], dp[i_{son}][0]))，上司没有参加舞会，其直系下属可以参加，也可以不参加。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int head[N], to[N], nex[N], in[N], cnt = 1;
int dp[N][2], n;
void add(int x, int y) {
to[cnt] = y;
nex[cnt] = head[x];
head[x] = cnt++;
in[y]++;
}
void dfs(int rt, int fa) {
for(int i = head[rt]; i; i = nex[i]) {
if(to[i] != fa) {
dfs(to[i], rt);
dp[rt][1] += dp[to[i]][0];
dp[rt][0] += max(dp[to[i]][0], dp[to[i]][1]);
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
while(scanf("%d", &n) != EOF) {
cnt = 1;
for(int i = 1; i <= n; i++) {
scanf("%d", &dp[i][1]);
head[i] = 0;
dp[i][0] = 0;
}
int x, y;
while(scanf("%d %d", &x, &y) && (x + y))
add(y, x);
for(int i = 1; i <= n; i++)
if(!in[i]) {
dfs(i, 0);
printf("%d
", max(dp[i][0], dp[i][1]));
}
}
return 0;
}
一道比入门题还简单的题
P2996 [USACO10NOV]Visiting Cows G
代码
入门题都懂了，这题想必大佬们肯定能写。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int head[N], to[N], nex[N], cnt = 1;
int dp[N][2], n;
void add(int x, int y) {
to[cnt] = y;
nex[cnt] = head[x];
head[x] = cnt++;
}
void dfs(int rt, int fa) {
for(int i = head[rt]; i; i = nex[i]) {
if(to[i] != fa) {
dfs(to[i], rt);
dp[rt][1] += dp[to[i]][0];
dp[rt][0] += max(dp[to[i]][0], dp[to[i]][1]);
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
int x, y;
scanf("%d", &n);
for(int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
dp[i][1] = 1;
}
dp[n][1] = 1;
dfs(1, 0);
printf("%d
", max(dp[1][0], dp[1][1]));
return 0;
}
一道思路对了，但是细节把我击垮了的题目
思路
思路不难，dp[i][j]数组，记录的时第i个节点加上其子树上与其相连的节点的数量时j时，需要切断的路径显然有dp[i][1] = 与其直接相连的子树加上一个父节点的路径。
然后状态转移方程就有了 (dp[i][j] = min(dp[i][j], dp[i][k] + dp[i_{son}][j - k] - 2))，这个减二的操作是因为，这两个之间相连的边都在互相的dp数组中记录了，所以需要减去2。
接下来就要说一个细节了，我们在最后的答案中dp[root][]中所有的都要减去1，因为在之前我们把其父节点的边加进去了，但是他是没有父节点的。这个点，坑人啊，还是太菜了。
代码
// #include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 2e2 + 10;
int head[N], to[N], nex[N], in[N], cnt;
int dp[N][N], sz[N], n, m;
void add(int x, int y) {
to[cnt] = y;
nex[cnt] = head[x];
head[x] = cnt++;
in[y]++;
}
void dfs1(int rt, int fa) {//寻找直接相连的结点数，初始化dp数组。
sz[rt] = 1;
for(int i = head[rt]; i; i = nex[i]) {
if(to[i] != fa) {
dfs1(to[i], rt);
sz[rt] ++;
}
}
}
void solve(int rt, int fa) {
for(int i = head[rt]; i ; i = nex[i]) {
if(to[i] != fa) {
solve(to[i], rt);
for (int j = m; j > 1; j--)
for (int k = 1; k < j; k++)
dp[rt][j] = min(dp[rt][j], dp[rt][j - k] + dp[to[i]][k] - 2);
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
int x, y;
while(scanf("%d %d", &n, &m) != EOF) {
memset(head, 0, sizeof head);
memset(dp, 0x3f, sizeof dp);
cnt = 1;
for(int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
add(x, y);
}
for(int i = 1; i <= n; i++)
if(in[i] == 0) {
// cout << i << endl;
dfs1(i, 0);
}
for(int i = 1; i <= n; i++)//好像可以直接在dfs1中完成，，，，
dp[i][1] = sz[i];
// cout << sz[i] << endl;
for(int i = 1; i <= n; i++)
if(in[i] == 0) {
solve(i, 0);
dp[i][m]--;
}
// for(int i = 1; i <= n; i++)//调试bug_ing
// for(int j = 1; j <= m; j++) {
// printf("%d%c", dp[i][j], j == m ? '
' : ' ');
// }
int ans = 0x3f3f3f3f;
for(int i = 1; i <= n; i++)
dp[i][m] < ans ? ans = dp[i][m] : ans = ans;//终于出答案了，写了一长串我现在看不懂的表达式，，，，
printf("%d
", ans);
}
return 0;
}
一道稍微复杂一点的题目
其实也挺好理解的。
思路
这是一道要自己建图的题，显然我们不难想到，在dis = 1的两个点之间建立联通的边，接下来的事情就是树上DP了。
考虑状态转移方程，对于每一个点我们可以将其放入联通集或者不放入联通集，同时我们还要保证，每一个点对都是互相连通的。
我们用dp[i][0]表示这个点不在联通集上，用dp[i][1]表示这个点在联通集上。
考虑dp[i][0]如何变化，不难发现他的值一定是其子树上的最大值，所以 (dp[i][0] = max(dp[i][0], dp[i_{son}][1], dp[i_{son}][0]))
接着我们考虑dp[i][1]，我们要保证它的连通性，得到 (dp[i][1] = max(dp[i][1], dp[i_{son}][1] + dp[i][1]))
然后按照这个思路跑一遍DFS就行了。
代码
// #include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N1 = 1e3 + 10, N2 = 1e6 + 10;
int head[N1], to[N2], nex[N2], cnt;
int dp[N1][2], n;
struct point {
int x, y;
}a[N1];
void add(int x, int y) {
to[cnt] = y;
nex[cnt] = head[x];
head[x] = cnt++;
}
void dfs(int rt, int fa) {
for(int i = head[rt]; i; i = nex[i]) {
if(to[i] != fa) {
// cout << 1 << endl;
dfs(to[i], rt);
dp[rt][1] = max(dp[rt][1], dp[rt][1] + dp[to[i]][1]);
dp[rt][0] = max(dp[rt][0], max(dp[to[i]][0], dp[to[i]][1]));
}
}
}
int main() {
// freopen("in.txt", "r", stdin);
int x, y, w;
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; i++)
dp[i][0] = dp[i][1] = head[i] = 0;
cnt = 1;
for(int i = 1; i <= n; i++) {
scanf("%d %d %d", &a[i].x, &a[i].y, &w);
dp[i][1] = w;
}
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
if((abs(a[i].x - a[j].x) + abs(a[i].y - a[j].y)) == 1) {
add(i, j), add(j, i);
// cout << 1 << endl;
}
dfs(1, 0);
// for(int i = 1; i <= n; i++)
// printf("%d %d
", dp[i][0], dp[i][1]);
printf("%d
", max(dp[1][0], dp[1][1]));
}
return 0;
}
本来应该还有第四道题，没想到考察了树上背包，但是这个东西我还没学过啊，就先咕咕咕咕咕下了。