2019牛客暑期NOIP真题班普及组10-DP2

1. 传球游戏

来源：NOIP2008普及组 https://ac.nowcoder.com/acm/contest/236/B

算法知识点：DP,环形DP

复杂度：

解题思路：

不妨设小蛮在0号，所有人的编号是 。

状态表示 f[i, j]：

• 集合：所有已经传了i次球，且最后球在编号是j的小朋友手上的方案；
• 属性：集合中元素的数量；

状态计算：

• f[i, j]所表示的集合可以划分成两个子集：
  • 从左边传过来的集合大小是f[i, j - 1]；
  • 从右边传过来的集合大小是f[i, j + 1]；
• f[i, j]等于两个子集的元素数之和。

注意当j = 0或j = n - 1时需要特殊处理边界。

最终答案就是f[[m][0]。

C++ 代码：

#include <iostream>

using namespace std;

const int N = 35;

int n, m;
int f[N][N];

int main()
{
    cin >> n >> m;

    f[0][0] = 1;
    for (int i = 1; i <= m; i ++ )
        for (int j = 0; j < n; j ++ )
            f[i][j] = f[i - 1][(j + n - 1) % n] + f[i - 1][(j + 1) % n];

    cout << f[m][0] << endl;

    return 0;
}

2. 道路游戏

来源：NOIP2009普及组 https://ac.nowcoder.com/acm/contest/237/B

算法知识点：DP,斜线型DP,堆

复杂度：

解题思路：

状态表示：

• f[i]表示前i单位时间内可获取的最多金币数；
• s[i, j]表示从[i, j]开始向左上角走的路径上的金币数量之和，注意如果走到第一行，则跳至最后一行继续走；
• cost[i]表示从第i个点购买机器需要花费的金币数；

状态转移：

• f[i] = max{f[i - k] + s[j, i] - s[j - k, i - k] - cost[j - k + 1]}，其中1 <= k <= i, k <= p, 1 <= j <= n；

整理一下可得：

• f[i] = max{f[i - k] - s[j - k, i - k] - cost[j - k + 1]} + s[j, i]

我们令g[i, j] = f[i] - s[i, j] - cost[j + 1]，则：

• f[i] = max{g[i - k][j - k]} + s[j, i]，其中1 <= k <= i, k <= p, 1 <= j <= n；

其中有三个变量，需要 的计算量，因此需要优化。

我们发现状态转移方程是对长度为 的滑动窗口求最大值，因此可以用单调队列或者堆可以去掉一重循环。

这里为了思路简单，我们选择堆来优化。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;

int n, m, p;
int s[N][N], cost[N];
int f[N], g[N][N];

struct Node
{
    int v, i, j;
    bool operator< (const Node& W)const
    {
        return v < W.v;
    }
};

priority_queue<Node>heap[N];

int get(int x)
{
    x %= n;
    if (x <= 0) x += n;
    return x;
}

int main()
{
    scanf("%d%d%d", &n, &m, &p);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &s[i][j]);

    for (int j = 1; j <= m; j ++ )
        for (int i = 1; i <= n; i ++ )
            if (i == 1) s[i][j] += s[n][j - 1];
            else s[i][j] += s[i - 1][j - 1];

    memset(f, -0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);
    f[0] = 0;

    for (int i = 1; i <= n; i ++ ) scanf("%d", &cost[i]);
    for (int i = 1; i < n; i ++ ) g[0][i] = -cost[i + 1], heap[get(-i)].push({-cost[i + 1], 0, i});
    g[0][n] = -cost[1], heap[get(-n)].push({-cost[1], 0, n});


    for (int i = 1; i <= m; i ++ )
    {
        for (int j = 1; j <= n; j ++ )
        {
            auto &h = heap[get(i - j)];
            while (h.size())
            {
                auto top = h.top();
                if (i - p > top.i) h.pop();
                else
                {
                    f[i] = max(f[i], s[j][i] + top.v);
                    break;
                }
            }
        }

        for (int j = 1; j <= n; j ++ )
        {
            g[i][j] = f[i] - s[j][i] - (j == n ? cost[1] : cost[j + 1]);
            heap[get(i - j)].push({g[i][j], i, j});
        }
    }

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

    return 0;
}

3. 表达式的值

来源：NOIP2011普及组 https://ac.nowcoder.com/acm/contest/239/A

算法知识点：DP,树形DP,栈,表达式求值

复杂度：

解题思路：

每一个中缀表达式都对应一棵满二叉树：

• 叶节点是数值；
• 内部节点是操作符，可能是+, *；

然后树形DP即可，每个节点存两个状态：该节点等于0的方案数、该节点等于1的方案数。

实际上我们也不需要将二叉树重建出来，直接在用栈模拟的过程中DP即可，这是因为栈模拟的顺序和深度优先遍历二叉树的顺序是相同的。

另外还要考虑在哪加入叶节点：

• 括号并不影响叶节点的位置，所以可以先忽略所有括号；
• 在剩下的每两个操作符之间填上数即可；

C++ 代码：

#include <iostream>
#include <algorithm>
#include <stack>
#include <map>

using namespace std;

const int mod = 10007;

struct State
{
    int one, zero;
};

stack<char> stk_op;
stack<State> stk_st;

void eval()
{
    auto op = stk_op.top(); stk_op.pop();
    auto a = stk_st.top(); stk_st.pop();
    auto b = stk_st.top(); stk_st.pop();

    if (op == '+') stk_st.push({(a.zero * b.one + a.one * b.zero + a.one * b.one) % mod, a.zero * b.zero % mod});
    else stk_st.push({a.one * b.one % mod, (a.one * b.zero + a.zero * b.one + a.zero * b.zero) % mod});
}

int main()
{
    int n;
    string expr;
    cin >> n >> expr;

    map<char, int> pr;
    pr['+'] = 1, pr['*'] = 2, pr['('] = 0;

    stk_st.push({1, 1});
    for (auto c : expr)
    {
        if (c == '(') stk_op.push(c);
        else if (c == '+' || c == '*')
        {
            while (stk_op.size() && pr[stk_op.top()] >= pr[c]) eval();
            stk_op.push(c);
            stk_st.push({1, 1});
        }
        else
        {
            while (stk_op.top() != '(') eval();
            stk_op.pop();
        }
    }

    while (stk_op.size()) eval();

    cout << stk_st.top().zero << endl;

    return 0;
}

4. 摆花

来源：NOIP2012普及组 https://ac.nowcoder.com/acm/contest/240/B

算法知识点：DP,多重背包问题,背包问题求方案数

复杂度：

解题思路：

问题转化：

• 将花盆数量看作背包容量；
• 将花看作物品，体积是1，第 种物品最多选 个；
• 问题：将背包装满的方案数是多少？

这是典型的多重背包求方案数问题：

• 状态表示：f[i, j] 表示前i个物品，总体积是j的方案数；
• 状态计算：f[i, j] = f[i - 1, j] + f[i - 1, j - 1] + ... + f[i - 1, j - a[i]]。

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, mod = 1000007;

int n, m;
int f[N];

int main()
{
    cin >> n >> m;

    f[0] = 1;
    for (int i = 0; i < n; i ++ )
    {
        int a;
        cin >> a;
        for (int j = m; j >= 0; j -- )
            for (int k = 1; k <= j && k <= a; k ++ )
                f[j] = (f[j] + f[j - k]) % mod;
    }

    cout << f[m] << endl;

    return 0;
}