dp,树形 dp + 换根,背包
# A. SP283 NAPTIME - Naptime
先假设不能构成环,考虑如何 。
设 表示到了第 个时间,已经连着睡了 个时间,当前是否睡觉,0 表示不睡,1 表示睡。
那么显然有转移方程:
但是时间是可以循环的,如何处理呢?
我们强制可以得到时间 1 的效用值即可,也就是强行把 1 和 连起来了。
这样为什么可以呢?
考虑如果我们没有得到时间 1 的效用值,那么即使时间可以循环也是无所谓的,所以这要就足够了。
我们只需要在赋初值时令 ,且最后统计答案时只对 取较小值即可。
#include <bits/stdc++.h> | |
#define pb push_back | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 4010; | |
int T, n, m, ans; | |
int w[N], s[N], dp[N][N][2]; | |
inline void dp1(){ | |
memset(dp, 128, sizeof(dp)); | |
dp[1][1][1] = dp[1][0][0] = 0; | |
for(int i = 2; i <= n; ++i) | |
for(int j = 0; j <= min(n, m); ++j){ | |
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]); | |
if(j) dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + w[i]); | |
} | |
ans = max(dp[n][m][0], dp[n][m][1]); | |
} | |
inline void dp2(){ | |
memset(dp, 128, sizeof(dp)); | |
dp[1][1][1] = w[1]; | |
for(int i = 2; i <= n; ++i) | |
for(int j = 0; j <= min(n, m); ++j){ | |
dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]); | |
if(j) dp[i][j][1] = max(dp[i - 1][j - 1][0], dp[i - 1][j - 1][1] + w[i]); | |
} | |
ans = max(ans, dp[n][m][1]); | |
} | |
inline void solve(){ | |
n = read(), m = read(), ans = 0; | |
for(int i = 1; i <= n; ++i) w[i] = read(); | |
dp1(), dp2(); | |
write(ans), puts(""); | |
} | |
signed main(){ | |
#ifndef ONLINE_JUDGE | |
freopen("test.in", "r", stdin); | |
freopen("test.out", "w", stdout); | |
#endif | |
T = read(); | |
while(T--) solve(); | |
return 0; | |
} |
# B. P3047 [USACO12FEB]Nearby Cows G
朴素的换根 。
设 表示 子树内距离 长度为 的点的权值和。
先以 1 为根,跑一遍树形 ,此时的 为 1 的答案。
然后我们来换根。
设要把根从 换到 ,那么转移:
执行完之后再:
后面这个一定要在前面全都更新完之后再更新。
更新之后递归处理,最后再改回来。
非常板子。
#include <bits/stdc++.h> | |
#define pb push_back | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 1e5 + 10; | |
int n, m; | |
int w[N], ans[N]; | |
vector <int> g[N]; | |
int f[N][23]; | |
inline void dfs(int x, int fa){ | |
f[x][0] = w[x]; | |
for(auto y : g[x]){ | |
if(y == fa) continue; | |
dfs(y, x); | |
for(int i = 1; i <= m; ++i) f[x][i] += f[y][i - 1]; | |
} | |
} | |
inline void solve(int x, int fa){ | |
for(int i = 0; i <= m; ++i) ans[x] += f[x][i]; | |
for(auto y : g[x]){ | |
if(y == fa) continue; | |
for(int i = 1; i <= m; ++i) f[x][i] -= f[y][i - 1]; | |
for(int i = 1; i <= m; ++i) f[y][i] += f[x][i - 1]; | |
solve(y, x); | |
for(int i = 1; i <= m; ++i) f[y][i] -= f[x][i - 1]; | |
for(int i = 1; i <= m; ++i) f[x][i] += f[y][i - 1]; | |
} | |
} | |
signed main(){ | |
#ifndef ONLINE_JUDGE | |
freopen("test.in", "r", stdin); | |
freopen("test.out", "w", stdout); | |
#endif | |
n = read(), m = read(); | |
for(int i = 1; i < n; ++i){ | |
int u = read(), v = read(); | |
g[u].pb(v), g[v].pb(u); | |
} | |
for(int i = 1; i <= n; ++i) w[i] = read(); | |
dfs(1, 0), solve(1, 0); | |
for(int i = 1; i <= n; ++i) write(ans[i]), puts(""); | |
return 0; | |
} |
# C. CF730J Bottles
第一问直接贪心求解。
然后第二问直接 背包,我们需要不移动的水的体积最大。
设 表示取了 个水杯,容积为 时最大的不移动的水的体积。
转移方程:
#include <bits/stdc++.h> | |
#define pb push_back | |
using namespace std; | |
namespace IO{ | |
inline int read(){ | |
int x = 0; | |
char ch = getchar(); | |
while(!isdigit(ch)) ch = getchar(); | |
while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar(); | |
return x; | |
} | |
template <typename T> inline void write(T x){ | |
if(x < 0) putchar('-'), x = -x; | |
if(x > 9) write(x / 10); | |
putchar(x % 10 + '0'); | |
} | |
} | |
using namespace IO; | |
const int N = 110; | |
int n, suma, sumb, tmp, cnt, ans; | |
int a[N], b[N], f[N][N * N]; | |
priority_queue <int> qb; | |
signed main(){ | |
#ifndef ONLINE_JUDGE | |
freopen("test.in", "r", stdin); | |
freopen("test.out", "w", stdout); | |
#endif | |
n = read(); | |
for(int i = 1; i <= n; ++i) a[i] = read(), suma += a[i]; | |
for(int i = 1; i <= n; ++i) b[i] = read(), sumb += b[i], qb.push(b[i]); | |
tmp = suma; | |
while(suma > 0) suma -= qb.top(), cnt++, qb.pop(); | |
memset(f, 128, sizeof(f)); | |
f[0][0] = 0; | |
for(int i = 1; i <= n; ++i) | |
for(int j = sumb; j >= b[i]; --j) | |
for(int k = 1; k <= cnt; ++k) | |
f[k][j] = max(f[k][j], f[k - 1][j - b[i]] + a[i]); | |
for(int i = tmp; i <= sumb; ++i) ans = max(ans, f[cnt][i]); | |
write(cnt), putchar(' '), write(tmp - ans), puts(""); | |
return 0; | |
} |