输入输出样例
输入样例#1：
5 2
1 0
2 1
3 2
4 3
输出样例#1：
3
输入样例#2：
9 5
0 1
0 2
2 6
4 2
8 1
1 3
3 7
3 5
输出样例#2：
5
说明
【输入输出样例 1 说明】
从格点 0 出发移动 2 步。经过 0, 1, 2 这 3 个格点。
【输入输出样例 2 说明】
一种可行的移动路径为 0 → 1 → 3 → 5 → 3 → 7，经过 0, 1, 3, 5, 7 这 5 个格点。
【数据规模与约定】
对于 100%的测试点，N,V ≤ 100, 0 ≤a_i,b_i< V
完了我一开始没管循环顺序写挂了
(f[0/1][i][j])表示从点i开始花费j步的最大收益,0/1表示最后不回到点i / 最后回到点i
然后就直接树上背包就好了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 205 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m ;
int hea[M] , num ;
struct E {
int Nxt , to ;
}edge[M << 2];
inline void add_edge(int from , int to) {
edge[++num].Nxt = hea[from] ;
edge[num].to = to ;
hea[from] = num ;
}
int f[2][M][M] ;
void Dfs(int u , int father) {
for(int i = 0 ; i <= m ; i ++) f[0][u][i] = f[1][u][i] = 1 ;
for(int i = hea[u] ; i ; i = edge[i].Nxt) {
int v = edge[i].to ;
if(v == father) continue ;
Dfs(v , u) ;
for(int j = m ; j >= 1 ; j --)
for(int k = 1 ; k <= j ; k ++) {
f[0][u][j] = max(f[0][u][j] , f[1][u][j - k] + f[0][v][k - 1]) ;
if(k >= 2) {
f[0][u][j] = max(f[0][u][j] , f[0][u][j - k] + f[1][v][k - 2]) ;
f[1][u][j] = max(f[1][u][j] , f[1][u][j - k] + f[1][v][k - 2]) ;
}
}
}
}
int main() {
n = read() ; m = read() ;
for(int i = 1 , u , v ; i < n ; i ++) {
u = read() + 1 , v = read() + 1 ;
add_edge(u , v) ;
add_edge(v , u) ;
}
Dfs(1 , 1) ;
printf("%d
",f[0][1][m]) ;
return 0 ;
}
然后还有一种做法是贪心
显然ta如果要回到原来的点,那么步数就是(收益-1)*2
所以我们可以先让ta在树根边上转一圈最后再顺着最长链走到底
#include<cstdio>
#include<algorithm>
const int M = 205 ;
using namespace std ;
inline int read() {
char c = getchar() ; int x = 0 , w = 1 ;
while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
return x*w ;
}
int n , m ;
int maxdep , Ans ;
struct E {
int Nxt , to ;
}edge[M << 1] ;
int hea[M] , num ;
inline void add_edge(int from , int to) {
edge[++num].Nxt = hea[from] ;
edge[num].to = to ;
hea[from] = num ;
}
void Dfs(int u , int father , int depth) {
maxdep = max(maxdep , depth) ;
for(int i = hea[u] , v ; i ; i = edge[i].Nxt) {
v = edge[i].to ;
if(v == father) continue ;
Dfs(v , u , depth + 1) ;
}
}
int main() {
n = read() ; m = read() ;
for(int i = 1 , u , v ; i < n ; i ++) {
u = read() + 1 , v = read() + 1 ;
add_edge(u , v) ; add_edge(v , u) ;
}
Dfs(1 , 1 , 0) ;
if(m <= maxdep + 1) Ans = m + 1 ;
else Ans = min(n , maxdep + 1 + (m - maxdep) / 2) ;
printf("%d
",Ans) ;
return 0 ;
}