把某周做过的题稍微整理了一下，主要是DP，方便随时复习，也方便后人踩坑。

1 完全背包 · 洛谷 P1616 疯狂的采药

思路
把「时间」看成背包容量，「价值」就是药草收益。每种药草可以无限次采集 ⇒ 完全背包。

状态转移 

1
dp[j] = max(dp[j], dp[j - h[i]] + w[i])

代码

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;
const int N = 1e4 + 10;
typedef long long ll;
int h[N], w[N];
const int M = 1e7 + 10;
ll dp[M];
int main()
{
    int t, m;
    scanf("%d%d", &t, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &h[i], &w[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = h[i]; j <= t; j++)
        {
            dp[j] = max(dp[j - h[i]] + w[i], dp[j]);
        }
    }
    printf("%lld\n", dp[t]);
    return 0;
}

2 混合背包 · 洛谷 P1833 樱花

思路
题目同时出现 01、多重、完全三种背包。

  • p[i] == 0 → 完全背包
  • p[i] > 0 → 01 / 多重背包

状态转移
完全背包：正序
多重背包：拆成 01 后逆序

代码

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;
const int N = 1e4 + 10;
int t[N], w[N], p[N];
int dp[1008];
int main()
{
    int h1, h2, m1, m2;
    scanf("%d:%d %d:%d", &h1, &m1, &h2, &m2);
    int n;
    scanf("%d", &n);
    int ans = (m2 - m1) + (h2 - h1) * 60;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &t[i], &w[i], &p[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        if (p[i] == 0) //完全背包
        {
            for (int j = t[i]; j <= ans; j++)
            {
                dp[j] = max(dp[j - t[i]] + w[i], dp[j]);
            }
        }
        else //多重背包和01背包
        {
            for (int k = 1; k <= p[i]; k++)
            {
                for (int j = ans; j >= k * t[i]; j--)
                {
                    dp[j] = max(dp[j - t[i]] + w[i], dp[j]);
                }
            }
        }
    }
    printf("%d\n", dp[ans]);
    return 0;
}

3 二维背包 · 洛谷 P1855 榨取kkksc03

思路
背包有两个限制维度：时间 & 金钱 ⇒ 二维 01 背包。

状态转移

1
dp[j][k] = max(dp[j][k], dp[j - a[i]][k - b[i]] + 1)

代码

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;
int a[108], b[108];
int dp[300][300];
int main()
{
    int n, m, t;
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i], &b[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= a[i]; j--)
        {
            for (int k = t; k >= b[i]; k--)
            {
                dp[j][k] = max(dp[j][k], dp[j - a[i]][k - b[i]] + 1);
            }
        }
    }
    printf("%d\n", dp[m][t]);
    return 0;
}

4 分组背包 · 洛谷 P1757 通天之分组背包

思路
物品分多组，每组最多选一个 ⇒ 经典分组背包。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int cnt[N];
int dp[N];
int a[N], b[N];
int vis[N][N];
int main()
{
    int m, n;
    scanf("%d%d", &m, &n);
    int ans;
    int maxn = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i], &b[i], &ans);
        ++cnt[ans];
        vis[ans][cnt[ans]] = i;
        maxn = max(maxn, ans);
    }
    for (int i = 1; i <= maxn; i++)
    {
        for (int j = m; j >= 0; j--)
        {
            for (int k = 1; k <= cnt[i]; k++)
            {
                if (j >= a[vis[i][k]])
                {
                    dp[j] = max(dp[j], dp[j - a[vis[i][k]]] + b[vis[i][k]]);
                }
            }
        }
    }
    printf("%d\n", dp[m]);
    return 0;
}

5 带附件的 01 背包 · 洛谷 P1064 [NOIP2006 提高组] 金明的预算方案

思路
每个主件最多带 2 个附件，决策从 2 种变成 5 种：
不选、只选主件、主件 + 附件1、主件 + 附件2、主件 + 全部附件。

代码

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;
const int N = 4e4 + 10;
int dpmainv[N], dpmainw[N];
int dpannexv[N][3], dpannexw[N][3];
int cnt[N];
int dp[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int a, b, q;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &a, &b, &q);
        if (q == 0)
        {
            dpmainv[i] = a;
            dpmainw[i] = a * b;
        }
        else
        {
            cnt[q]++;
            dpannexv[q][cnt[q]] = a;
            dpannexw[q][cnt[q]] = a * b;
        }
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = n; j >= dpmainv[i] && dpmainv[i] > 0; j--)
        {
            dp[j] = max(dp[j], dp[j - dpmainv[i]] + dpmainw[i]);
            if (j >= dpmainv[i] + dpannexv[i][1])
            {
                dp[j] = max(dp[j], dp[j - dpmainv[i] - dpannexv[i][1]] + dpmainw[i] + dpannexw[i][1]);
            }
            if (j >= dpmainv[i] + dpannexv[i][2])
            {
                dp[j] = max(dp[j], dp[j - dpmainv[i] - dpannexv[i][2]] + dpmainw[i] + dpannexw[i][2]);
            }
            if (j >= dpmainv[i] + dpannexv[i][1] + dpannexv[i][2])
            {
                dp[j] = max(dp[j], dp[j - dpmainv[i] - dpannexv[i][1] - dpannexv[i][2]] + dpmainw[i] + dpannexw[i][1] + dpannexw[i][2]);
            }
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}

6 树形 DP · 洛谷 P1352 没有上司的舞会

思路
树上做 01 背包：

  • dp[u][0] 不参加，儿子可选可不选
  • dp[u][1] 参加，儿子不能参加

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 6e3 + 10;
int a[N];
int dp[N][2];
int vis[N];
vector<int> v[N];
void dfs(int ans)
{
    dp[ans][1] = a[ans];
    for (int i = 0; i < v[ans].size(); i++)
    {
        int cnt = v[ans][i];
        dfs(cnt);                                  //往下遍历
        dp[ans][0] += max(dp[cnt][0], dp[cnt][1]); //他的下属参加还是不参加
        dp[ans][1] += dp[cnt][0];                  //此时下属不能参加
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    int p, q;
    for (int i = 1; i <= n - 1; i++)
    {
        scanf("%d%d", &p, &q);
        v[q].push_back(p);
        vis[p] = 1; //把职员标记上
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0) //找最高职位，也就是树的根
        {
            ans = i;
            break;
        }
    }
    dfs(ans);
    printf("%d\n", max(dp[ans][0], dp[ans][1]));
    return 0;
}

7 区间 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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e2 + 10;
int a[N];
int dp[N][N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i + n] = a[i];
    }
    // 2 3 5 10 2 3 5 10
    //还是环形石子问题
    for (int len = 3; len <= n + 1; len++) //最少要三个值才能聚合两个珠子，但最后一个值最后还会用到
    {
        for (int l = 1; l + len - 1 <= 2 * n; l++)
        {
            int r = l + len - 1;
            for (int k = l + 1; k < r; k++) //由于每颗珠子分首尾，所以k最小也得是l+1
            {
                dp[l][r] = max(dp[l][r], dp[l][k] + dp[k][r] + a[l] * a[k] * a[r]); //由于k位置这个元素会重复用到，所以不用加一！！！
            }
        }
    }
    int maxn = 0;
    for (int i = 1; i <= n; i++)
    {
        maxn = max(maxn, dp[i][n + i]);
        // printf("%d\n", dp[i][i + n]);
    }
    printf("%d\n", maxn);
    return 0;
}

8 第 k 优解 · HDU 2639

思路
在 01 背包基础上多开一维 dp[j][k] 记录体积为 j 时的前 k 大值。

核心技巧
每次用归并排序思想把两条链（选/不选）的前 k 大合并。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int dp[N][N];
int a[108], b[108];
int c[108], d[108];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(dp, 0, sizeof(dp));
        memset(c, 0, sizeof(c));
        memset(d, 0, sizeof(d));
        int n, v, p;
        scanf("%d%d%d", &n, &v, &p);
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &b[i]);
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = v; j >= b[i]; j--)
            {
                for (int k = 1; k <= p; k++)
                {
                    c[k] = dp[j][k]; //体积为j时的第k大价值
                    d[k] = dp[j - b[i]][k] + a[i];
                }
                int q = 1, l = 1, r = 1;
                while (q <= p && (l <= p || r <= p))
                {
                    if (c[l] >= d[r]) //比较两个数的大小，谁大就用谁赋值
                    {
                        dp[j][q] = c[l++];
                    }
                    else
                    {
                        dp[j][q] = d[r++];
                    }
                    if (dp[j][q] != dp[j][q - 1]) //这里要去一下重
                    {
                        q++;
                    }
                }
            }
        }
        printf("%d\n", dp[v][p]);
    }
    return 0;
}

9 线段树/搜索 · HDU 5323

思路
根据父子区间关系做 DFS，剪枝：右端点大于当前答案或左端点越界时返回。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
void dfs(ll l, ll r) //建立左区间和右区间递归搜索
{
    if (l == 0)
    {
        if (r != 0)
        {
            ans = min(ans, r);
        }
    }
    if (r >= ans) //右边界
    {
        return;
    }
    if (l - 1 - (r - l) < 0) //左边界
    {
        return;
    }
    dfs(l - 1 - (r - l), r); //奇数区间
    dfs(l, r + 1 + r - l);
    dfs(l - 1 - (r - l) - 1, r); //偶数区间
    dfs(l, r + 1 + r - l - 1);
}
int main()
{
    ll l, r;
    while (scanf("%lld%lld", &l, &r) != EOF)
    {
        ans = 0x3f3f3f3f;
        dfs(l, r);
        if (l == 0 && r == 0)
        {
            printf("0\n");
        }
        else
        {
            if (ans == 0x3f3f3f3f)
            {
                printf("-1\n");
            }
            else
            {
                printf("%lld\n", ans);
            }
        }
    }
    return 0;
}