暑假集训-week3-动态规划

A - 最大子段和

在这里插入图片描述
经典的最大子段和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
// 最大子段和(dp模板题)
// https://www.luogu.com.cn/problem/P1115
int a[200001];
int dp[200001];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    int ans = -9999999;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        dp[i] = max(dp[i - 1] + a[i], a[i]);
        ans = max(dp[i], ans);
    }
    cout << ans;
    return 0;
}

B - Max Sum Plus Plus

在这里插入图片描述

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
#include <bits/stdc++.h>
using namespace std;
// https://vjudge.csgrandeur.cn/contest/507882#problem/B
// 参考题解：https://blog.csdn.net/weixin_44035017/article/details/103318078?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165934103416782388023006%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=165934103416782388023006&biz_id=0&spm=1018.2226.3001.4187
// 二维dp+滚动数组优化
const int maxn = 1e6 + 9;
int n, m, a[maxn], dp[maxn], lastmax[maxn];
int remp_sum, sum;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    while (scanf("%d%d", &m, &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        memset(lastmax, 0, sizeof(lastmax));
        remp_sum = 0, sum = 0;
        for (int i = 1; i <= m; i++)
        {
            sum = -0x3f3f3f3f;
            for (int j = i; j <= n; j++)
            {
                dp[j] = max(dp[j - 1] + a[j], lastmax[j - 1] + a[j]);
                lastmax[j - 1] = sum;
                sum = max(sum, dp[j]);
            }
        }
        cout << sum << endl;
    }
    return 0;
}

C - Longest Ordered Subsequence

在这里插入图片描述
最大上升子序列模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
// 模板：最大上升子序列
const int maxn = 100010, INF = 0x7f7f7f7f;
int a[maxn], dp[maxn]; // dp[i]代表以a[i]结尾的子序列最大长度
int n, ans = -INF;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        dp[i] = 1;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                dp[i] = max(dp[i], dp[j] + 1);
    for (int i = 1; i <= n; i++)
        ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}

D - 采药

在这里插入图片描述

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
#include <bits/stdc++.h>
using namespace std;
// 01背包模板题
const int maxn = 10000;
int t, m;
int cost[maxn], value[maxn], bag[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> t >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> cost[i] >> value[i];
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = t; j >= cost[i]; j--)
        {
            bag[j] = max(bag[j - cost[i]] + value[i], bag[j]);
        }
    }
    cout << bag[t];
    return 0;
}

E - Piggy-Bank

在这里插入图片描述
在这里插入图片描述
完全背包分别求最大和求最小
求最小时先全统一赋值为无穷大，然后再将初始赋值为0
顺便快读的板子也在这里了

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
#include <bits/stdc++.h>
using namespace std;
// 传送门：https://vjudge.csgrandeur.cn/contest/507882#problem/E
// 完全背包
// 快读不能和清缓存一起用！
const int maxn = 100100;
int t, e, f, n, m; // n为个数，m为背包大小
int cost[maxn], value[maxn], bag[maxn];
inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
int main()
{
    t = read();
    while (t--)
    {
        memset(bag, 0x3f, sizeof(bag));
        e = read(), f = read(), n = read();
        m = f - e;
        for (int i = 1; i <= n; i++)
        {
            value[i] = read();
            cost[i] = read();
        }
        bag[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            int p = value[i];
            int w = cost[i];
            for (int j = w; j <= m; j++)
            {
                bag[j] = min(p + bag[j - w], bag[j]);
            }
        }
        if (bag[m] == 0x3f3f3f3f)
            cout << "This is impossible." << endl;
        else
            printf("The minimum amount of money in the piggy-bank is %d.\n", bag[m]);
    }

    return 0;
}

F - Dividing

在这里插入图片描述
在这里插入图片描述
多重背包的二进制优化

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
#include <bits/stdc++.h>
using namespace std;
// https://vjudge.csgrandeur.cn/contest/507882#problem/F
// 多重背包优化
// 二进制优化
int cnt[601000];
int sum;
int value[601000]; //此题不需要空间
int dp[601000];
inline int read()
{
    sum = 0;
    for (int i = 1; i <= 6; i++)
        cin >> cnt[i], sum += cnt[i] * i;
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int flag = 0;
    while (read())
    {
        memset(dp, 0, sizeof(dp));
        memset(value, 0, sizeof(value));
        printf("Collection #%d:\n", ++flag);
        if (sum % 2)
        {
            printf("Can't be divided.\n\n");
            continue;
        }
        int num = 0;
        for (int i = 1; i <= 6; i++)
        {
            int remp = cnt[i];
            int k = 1; //二进制个数
            while (k <= remp)
            {
                num++;
                value[num] = i * k;
                remp -= k;
                k *= 2;
            }
            if (remp > 0)
            {
                num++;
                value[num] = i * remp;
            }
        }
        sum /= 2;
        for (int i = 1; i <= num; i++)
            for (int j = sum; j >= value[i]; j--)
                dp[j] = max(dp[j], dp[j - value[i]] + value[i]); //注意传进max内的两个参数
        if (dp[sum] == sum)
            printf("Can be divided.\n\n");
        else
            printf("Can't be divided.\n\n");
    }
    return 0;
}

G - 石子合并

在这里插入图片描述
一个环形的链！！！
处理方法很有意思，直接将原链扩充二倍，在长度2*n的直链取一个长度n的链得到最大贡献值

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
#include <bits/stdc++.h>
using namespace std;
// 区间dp:https://www.luogu.com.cn/problem/P1880
// 因为是一个环形区间，我们可以通过将数组扩充两倍来实现
const int maxn = 330;
int n;
int a[maxn], sum[maxn], dp_min[maxn][maxn], dp_max[maxn][maxn];
inline int d(int i, int j)
{
    return sum[j] - sum[i - 1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    memset(dp_min, 0x3f3f3f3f, sizeof(dp_min));
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= 2 * n; i++)
    {
        a[i + n] = a[i];
        sum[i] = a[i] + sum[i - 1];
        dp_min[i][i] = 0;
    }
    for (int len = 1; len < n; len++)
    {
        for (int l = 1, r = l + len; (r <= n + n) && (l <= n + n); l++, r = l + len)
        {
            for (int k = l; k < r; k++) //这个地方是小于号！！！加了等于的话就超出边界了！
            {
                dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] + dp_max[k + 1][r] + d(l, r));
                dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] + dp_min[k + 1][r] + d(l, r));
            }
        }
    }
    int max1 = -0x3f3f3f3f, min1 = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++)
    {
        max1 = max(max1, dp_max[i][i + n - 1]);
        min1 = min(min1, dp_min[i][i + n - 1]);
    }
    cout << min1 << endl
         << max1 << endl;
    return 0;
}

H - 能量项链

在这里插入图片描述
首尾的处理很有意思
在这里插入图片描述

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
#include <bits/stdc++.h>
using namespace std;
// 区间dp
// https://www.luogu.com.cn/problem/P1063
const int maxn = 3 * 110;
int n;
int head[maxn], tail[maxn];
int dp[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> head[i];
        head[i + n] = head[i];
    }
    for (int i = 1; i <= 2 * n - 1; i++)
    {
        tail[i] = head[i + 1];
    }
    tail[2 * n] = head[1];
    for (int len = 2; len <= n; len++)
    {
        for (int l = 1, r = l + len - 1; (l <= 2 * n) && (r <= 2 * n); l++, r = l + len - 1)
        {
            for (int k = l; k < r; k++)
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k + 1][r] + head[l] * tail[k] * tail[r]);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res = max(res, dp[i][i + n -1]);
    }
    cout << res;
    return 0;
}

I - 没有上司的舞会

在这里插入图片描述
在这里插入图片描述
树形dp模板题，看注释
感觉树形dp的思路还是很清晰的

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
#include <bits/stdc++.h>
using namespace std;
int n;
int happy[6010], dp[6010][2];
// dp[x][1]:代表x节点参选，此时以x为根的子树贡献最大和
// dp[x][0]:代表x节点不参选，此时以x为根的子树贡献最大和
// 传送门：https://www.luogu.com.cn/problem/P1352
bool visit[6010];
vector<int> son[6010];
void search(int x) //搜索
{
    int fa = x;
    dp[x][1] = happy[x], dp[x][0] = 0;
    for (int i = 0; i < son[x].size(); i++)
    {
        int s = son[x][i];
        search(s);
        dp[x][1] += dp[s][0];
        dp[x][0] += max(dp[s][0], dp[s][1]);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> happy[i];
    }
    for (int i = 1; i <= n - 1; i++)
    {
        int l, k;
        cin >> l >> k;
        visit[l] = true; //他有父亲节点
        son[k].push_back(l);
    }
    int root; //找到根节点
    for (int i = 1; i <= n; i++)
        if (visit[i] == false)
        {
            root = i;
            break;
        }
    search(root);
    cout << max(dp[root][1], dp[root][0]);
    return 0;
}

J - 战略游戏

在这里插入图片描述

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
#include <bits/stdc++.h>
using namespace std;
// https://www.luogu.com.cn/problem/P2016
// 树形dp
const int maxn = 200000;
int n, dp[maxn][2];
vector<int> son[maxn];
int cnt;
bool visit[maxn];
void search(int x)
{
    dp[x][1] = 1, dp[x][0] = 0;
    int f = x;
    for (int i = 0; i < son[f].size(); i++)
    {
        int s = son[f][i];
        search(s);
        //若该点无士兵，则子节点必须全部都有士兵占据
        dp[f][0] += dp[s][1];
        // 若该点没有士兵，子节点有无士兵都可，只要最小就行
        dp[f][1] += min(dp[s][1], dp[s][0]);
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int k, tar;
        cin >> tar >> k;
        for (int j = 1; j <= k; j++)
        {
            int remp;
            cin >> remp;
            visit[remp] = true;
            son[tar].push_back(remp);
        }
    }
    int ans = 0, root = 0;
    for (int i = 0; i < n; i++)
        if (visit[i] == false)
        {
            root = i;
            break;
        }
    search(root);
    cout << min(dp[root][0], dp[root][1]);
    return 0;
}