2019牛客暑期NOIP真题班提高组8-DP1

1. 加分二叉树

来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/251/C

算法知识点: 区间DP，二叉树的遍历

复杂度： $O(n^3)$

解题思路：

状态表示：f[i][j] 表示中序遍历是 w[i ~ j] 的所有二叉树的得分的最大值。
状态计算：f[i][j] = max(f[i][k - 1] * f[k + 1][j] + w[k])，即将f[i][j]表示的二叉树集合按根节点分类，则根节点在 k 时的最大得分即为 f[i][k - 1] * f[k + 1][j] + w[k]，则f[i][j]即为遍历 k 所取到的最大值。

在计算每个状态的过程中，记录每个区间的最大值所对应的根节点编号。

那么最后就可以通过DFS求出最大加分二叉树的前序遍历了。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef pair <int, int> PII; const int N = 50;

int n;
int w[N];
unsigned f[N][N];
int root[N][N];

void dfs(int l, int r)
{
    if (l > r) return;

    int k = root[l][r];
    printf("%d ", k, f[l][r]);
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
    for (int len = 1; len <= n; len++)
        for (int l = 1; l + len - 1 <= n; l++)
        {
            int r = l + len - 1;

            for (int k = l; k <= r; k++)
            {
                int left = k == l ? 1 : f[l][k - 1];
                int right = k == r ? 1 : f[k + 1][r];
                int score = left *right + w[k];
                if (l == r) score = w[k];
                if (f[l][r] < score)
                {
                    f[l][r] = score;
                    root[l][r] = k;
                }
            }
        }

    printf("%d\n", f[1][n]);
    dfs(1, n);
    puts("");

    return 0;
}

2. 合唱队形

来源：NOIP2004提高组 https://ac.nowcoder.com/acm/contest/252/C

算法知识点: 线性DP，最长上升子序列

复杂度： $O(n^2)$

解题思路：

假设最优解的中心是第 $i$ 个人，则 $T\_1, T\_2, ..., T\_i$ 一定是以 $T\_i$ 结尾的最长上升子序列。
同理， $T\_K, T\_{K-1}, ..., T\_i$ 也一定是以 $T\_i$ 结尾的最长上升子序列。

因此可以先预处理出：

从前往后以每个点结尾的最长上升子序列长度 f[i]；
从后往前以每个点结尾的最长上升子序列长度 g[i]；

那么以 $k$ 为中心的最大长度就是 f[k] + g[k] - 1，遍历 k = 1, 2, ..., n 取最大值即为答案。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 110;

int n;
int h[N];
int f[N], g[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (h[j] < h[i])
                f[i] = max(f[i], f[j] + 1);
    }

    for (int i = n; i; i--)
    {
        g[i] = 1;
        for (int j = n; j > i; j--)
            if (h[j] < h[i])
                g[i] = max(g[i], g[j] + 1);
    }

    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i] + g[i] - 1);

    printf("%d\n", n - res);

    return 0;
}

3.过河

来源：NOIP2005提高组 https://ac.nowcoder.com/acm/contest/253/B

算法知识点: 动态规划，数学

复杂度： $O(mT^3)$

解题思路：

如果不考虑 $L$ 的范围，那么就是一道简单的DP问题：

状态表示 f[i] 表示走到位置 i，踩到的石头个数的最小值；
状态计算 f[i] = min(f[j]) + w[i], 其中 w[i] 表示第 i 个位置是否有石头，j 在 S 到 T 之间。

那么当 $L$ 很大时该怎么办呢，我们发现虽然 $L$ 是 $10^9$ 级别，但石头总数很少，最多只有 $100$ 个，因此两个石头之间可能有很长的“空隙”。

接下来分两种情况讨论：

如果 S == T，那么走法唯一，石头位置是 S 整数倍的一定会被踩，否则一定不会被踩，直接遍历一遍所有石头即可；
如果 S != T，那么我们考虑不能被 S, S+1, S+2, ..., T 所表示的数有哪些，如果我们只用两个相邻的数 $p, q$ ，那么不能被表示的数的最大值是 $(p - 1)(q - 1) - 1$ ，因此所有大于等于 $(p - 1)(q - 1)$ 的数一定可以被 $p, q$ 表示出来，当 $p = 9, q = 10$ 时取到最大值，此时 $(p - 1)(q - 1) = 72$ ，因此所有大于等于72的数，一定可以被 S, S+1, S+2, ..., T 表示出来。当第一次越过第 $i$ 个石头时，青蛙的位置一定在该石头右侧十步以内；当即将跳过第 $i + 1$ 个石头时，青蛙一定在第 $i + 1$ 个石头左侧十步以内。那么当中间部分的长度大于100时我们可以将线段的长度缩短为100，得到的结果是等价的。那么此时最多只会用到 $100 * 100 = 10000$ 个位置，复杂度可以接受了。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 10020;

int n, S, T, m;
int stones[N];
int w[N], f[N];

int main()
{
    scanf("%d%d%d%d", &n, &S, &T, &m);

    if (S == T)
    {
        int res = 0;
        while (m--)
        {
            int x;
            scanf("%d", &x);
            if (x % S == 0) res++;
        }
        printf("%d\n", res);
    }
    else
    {
        for (int i = 0; i < m; i++) scanf("%d", &stones[i]);
        sort(stones, stones + m);

        int last = 0, k = 0;
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < min(stones[i] - last, 100); j++)
                w[++k] = 0;
            w[k] = 1;
            last = stones[i];
        }
        for (int i = 1; i <= k + 10; i++)
        {
            f[i] = 1e9;
            for (int j = S; j <= T; j++)
                if (i - j >= 0)
                    f[i] = min(f[i], f[i - j] + w[i]);
        }
        int res = 1e9;
        for (int i = k + 1; i <= k + 10; i++) res = min(res, f[i]);

        printf("%d\n", res);
    }

    return 0;
}

4. 金明的预算方案

来源：NOIP2006提高组 https://ac.nowcoder.com/acm/contest/254/B

算法知识点: DP，分组背包问题

复杂度： $O(Nm)$

解题思路：

可以将每个主件及其附件看作一个物品组，记主件为 $p$ ，两个附件为 $a, b$ ，则最多一共有4种组合：

$p$
$p, a$
$p, b$
$p, a, b$

这四种组合是互斥的，最多只能从中选一种，因此可以将每种组合看作一个物品，那么问题就变成了分组背包问题。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

typedef pair <int, int> PII;
const int N = 70,
    M = 32010;

int m, n;
PII a[N];
vector<PII> b[N];
int f[M];

int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
    {
        int v, w, p;
        scanf("%d%d%d", &v, &w, &p);
        w *= v;
        if (!p) a[i] = {
            v, w
        };
        else b[p].push_back(
        {
            v, w
        });
    }

    for (int i = 1; i <= n; i++)
    {
        if (!a[i].first) continue;

        for (int j = m; j >= 0; j--)
            for (int k = 0; k < 1 << b[i].size(); k++)
            {
                int v = a[i].first, w = a[i].second;
                for (int u = 0; u < b[i].size(); u++)
                    if (k >> u &1)
                    {
                        v += b[i][u].first;
                        w += b[i][u].second;
                    }

                if (j >= v) f[j] = max(f[j], f[j - v] + w);
            }
    }

    printf("%d\n", f[m]);

    return 0;
}

另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ