题意：树上最长不相交k条链。
#include <cstdio>
#include <algorithm>
#include <cstring> typedef long long LL;
const int N = ; struct Edge {
int nex, v;
LL len;
}edge[N << ]; int top; LL f[N][][];
int e[N], n, k, siz[N]; inline void add(int x, int y, LL z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
} inline void exmax(LL &a, LL b) {
if(a < b) {
a = b;
}
return;
} void DFS(int x, int fa) {
siz[x] = ;
f[x][][] = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa) {
continue;
}
DFS(y, x);
siz[x] += siz[y];
// DP
for(int j = std::min(k, siz[x]); j >= ; j--) {
for(int p = ; p <= j && p <= siz[y]; p++) { // p in son
exmax(f[x][j][], f[x][j - p + ][] + f[y][p][] + edge[i].len);
exmax(f[x][j][], f[x][j - p][] + std::max(f[y][p][], std::max(f[y][p][], f[y][p][])));
exmax(f[x][j][], f[x][j - p][] + std::max(f[y][p][], std::max(f[y][p][], f[y][p][])));
exmax(f[x][j][], f[x][j - p][] + std::max(f[y][p][], std::max(f[y][p][], f[y][p][])));
exmax(f[x][j][], f[x][j - p][] + f[y][p][] + edge[i].len);
}
}
}
for(int i = ; i <= k && i <= siz[x]; i++) {
exmax(f[x][i][], f[x][i - ][]);
}
/*printf("x = %d \n", x);
for(int i = 0; i <= k && i <= siz[x]; i++) {
printf("%d || 0 : %lld 1 : %lld 2 : %lld \n", i, f[x][i][0], f[x][i][1], f[x][i][2]);
}*/
return;
} int main() {
int n;
memset(f, ~0x3f, sizeof(f));
scanf("%d%d", &n, &k);
k++;
int x, y;
LL z;
for(int i = ; i < n; i++) {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
DFS(, );
printf("%lld\n", std::max(std::max(f[][k][], f[][k][]), f[][k][]));
return ;
}
60分DP
解：带权二分/wqs二分/DP凸优化。
一个比较常见的套路吧。
一般是求解有k限制的最优化问题。且随着k的变化，极值函数上凸/下凸。
这时我们二分一个斜率去切它，会有一个斜率切到我们要的k。
感性理解一下，我们给这k个事物附上权值，然后权值增加的时候k就会变多，权值减小(可以为负)的时候k会变少。
然后会有某个权值使得不限制k时的最优值恰好选了k。这时候我们减去附加的权值即可。
本题就是给每条链加上一个权值。
还有一道题是k条白边，剩下的选黑边的最小生成树。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> typedef long long LL;
const int N = ;
const LL INF = 1e17; struct Edge {
int nex, v;
LL len;
}edge[N << ]; int top; LL f[N][], D;
int g[N][], n, k, e[N]; inline void add(int x, int y, LL z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
} inline void exmax(LL &a, int &c, LL b, int d) {
if(a < b || (a == b && c > d)) {
a = b;
c = d;
}
return;
} void DFS(int x, int fa) {
f[x][] = ; // 初始化 不选链
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa) {
continue;
}
DFS(y, x);
exmax(f[x][], g[x][], f[x][] + f[y][], g[x][] + g[y][]);
exmax(f[x][], g[x][], f[x][] + f[y][] + edge[i].len - D, g[x][] + g[y][] - ); // 1 -> 2 exmax(f[x][], g[x][], f[x][] + f[y][], g[x][] + g[y][]);
exmax(f[x][], g[x][], f[x][] + f[y][] + edge[i].len, g[x][] + g[y][]); // 0 -> 1 exmax(f[x][], g[x][], f[x][] + f[y][], g[x][] + g[y][]);
}
exmax(f[x][], g[x][], f[x][] + D, g[x][] + ); // 自己单独开链
exmax(f[x][], g[x][], f[x][], g[x][]);
exmax(f[x][], g[x][], f[x][], g[x][]);
return;
} inline bool check(LL mid) {
D = mid;
memset(g, , sizeof(g));
memset(f, ~0x3f, sizeof(f));
DFS(, );
//printf("D = %lld \nf = %lld g = %d \n\n", D, f[1][2], g[1][2]);
return ;
} int main() { scanf("%d%d", &n, &k);
LL z, r = , l;
k++;
for(int i = , x, y; i < n; i++) {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
add(y, x, z);
r += std::abs(z);
}
l = -r;
while(l < r) {
LL mid = (l + r + ) >> ;
//printf("%lld %lld mid = %lld \n", l, r, mid);
check(mid);
if(g[][] == k) {
printf("%lld\n", f[][] - k * mid);
return ;
}
if(g[][] > k) {
r = mid - ;
}
else {
l = mid;
}
} check(r);
printf("%lld\n", f[][] - k * r);
return ;
}
AC代码
本题只要整数二分就行了。
负数二分用右移，是向下取整。
细节：可能最优点不是凸包上的顶点，是一条边中间。我们这时找到靠左的那个顶点，然后用这个斜率 * k就行了。
实数版：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath> typedef long long LL;
const int N = ;
const LL INF = 1e17;
const double eps = 1e-; struct Edge {
int nex, v;
LL len;
}edge[N << ]; int top; double f[N][], D;
int g[N][], n, k, e[N]; inline void add(int x, int y, LL z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
} inline void exmax(double &a, int &c, double b, int d) {
// if(a < b || (a == b && c > d)) {
if(a < b) {
a = b;
c = d;
}
return;
} void DFS(int x, int fa) {
f[x][] = ; // 初始化 不选链
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa) {
continue;
}
DFS(y, x);
exmax(f[x][], g[x][], f[x][] + f[y][], g[x][] + g[y][]);
exmax(f[x][], g[x][], f[x][] + f[y][] + edge[i].len - D, g[x][] + g[y][] - ); // 1 -> 2 exmax(f[x][], g[x][], f[x][] + f[y][], g[x][] + g[y][]);
exmax(f[x][], g[x][], f[x][] + f[y][] + edge[i].len, g[x][] + g[y][]); // 0 -> 1 exmax(f[x][], g[x][], f[x][] + f[y][], g[x][] + g[y][]);
}
exmax(f[x][], g[x][], f[x][] + D, g[x][] + ); // 自己单独开链
exmax(f[x][], g[x][], f[x][], g[x][]);
exmax(f[x][], g[x][], f[x][], g[x][]);
return;
} inline bool check(double mid) {
D = mid;
memset(g, , sizeof(g));
//memset(f, ~0x3f, sizeof(f));
for(int i = ; i <= n; i++) {
f[i][] = f[i][] = f[i][] = -INF;
}
DFS(, );
//printf("D = %lld \nf = %lld g = %d \n\n", D, f[1][2], g[1][2]);
return ;
} int main() { scanf("%d%d", &n, &k);
LL z;
double r = , l;
k++;
for(int i = , x, y; i < n; i++) {
scanf("%d%d%lld", &x, &y, &z);
add(x, y, z);
add(y, x, z);
r += std::abs(z);
}
l = -r;
while(fabs(r - l) > eps) {
double mid = (l + r) / ;
//printf("%lld %lld mid = %lld \n", l, r, mid);
check(mid);
if(g[][] == k) {
printf("%.0f\n", f[][] - k * mid);
return ;
}
if(g[][] > k) {
r = mid;
}
else {
l = mid;
}
} check(r);
printf("%.0f\n", f[][] - k * r);
return ;
}
AC代码