首页 模拟赛

dp，树形dp + 换根，背包

# A. SP283 NAPTIME - Naptime

先假设不能构成环，考虑如何 dp\text{dp}。

设 dpi,j,0/1dp_{i, j, 0/1} 表示到了第 ii 个时间，已经连着睡了 jj 个时间，当前是否睡觉，0 表示不睡，1 表示睡。

那么显然有转移方程：

dpi,j,0=max⁡{dpi−1,j,1,dpi−1,j,0}dpi,j,1=max⁡{dpi−1,j−1,0,dpi−1,j−1,1+wi}dp_{i, j, 0} = \max\{dp_{i - 1, j, 1}, dp_{i - 1, j, 0} \} \\ dp_{i, j, 1} = \max\{dp_{i - 1, j - 1, 0}, dp_{i - 1, j - 1, 1} + w_i \}

但是时间是可以循环的，如何处理呢？

我们强制可以得到时间 1 的效用值即可，也就是强行把 1 和 nn 连起来了。

这样为什么可以呢？

考虑如果我们没有得到时间 1 的效用值，那么即使时间可以循环也是无所谓的，所以这要就足够了。

我们只需要在赋初值时令 dp1,1,1=w1dp_{1, 1, 1} = w_1，且最后统计答案时只对 dpn,b,1dp_{n, b, 1} 取较小值即可。

codecode

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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

朴素的换根 dp\text{dp}。

设 fx,if_{x, i} 表示 xx 子树内距离 xx 长度为 ii 的点的权值和。

先以 1 为根，跑一遍树形 dp\text{dp}，此时的 ∑i=0kf1,i\sum\limits_{i = 0}^kf_{1, i} 为 1 的答案。

然后我们来换根。

设要把根从 xx 换到 yy，那么转移：

fx,i−=fy,i−1 (i∈[1,k])f_{x, i} -= f_{y, i - 1}\ (i \in [1, k])

执行完之后再：

fy,i+=fx,i−1 (i∈[1,k])f_{y, i} += f_{x, i - 1}\ (i \in [1, k])

后面这个一定要在前面全都更新完之后再更新。

更新之后递归处理，最后再改回来。

非常板子。

codecode

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#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

第一问直接贪心求解。

然后第二问直接 0/1\text{0/1} 背包，我们需要不移动的水的体积最大。

设 fk,jf_{k, j} 表示取了 kk 个水杯，容积为 jj 时最大的不移动的水的体积。

转移方程：

fk,j=max⁡{fk−1,j−b[i]+ai}f_{k, j} = \max\{f_{k - 1, j - b[i]} + a_i \}

codecode

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
40
41
42
43
44
45
46
47
#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;
}

更新于 阅读次数 次