2019牛客暑期NOIP真题班普及组9-DP1

1. 数字游戏

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

算法知识点: DP,区间DP

复杂度：

解题思路：

首先将环从起点处断开，然后复制一遍接在后面，这样原问题就转化成了线段型的模型。

然后从集合角度来分析状态表示和状态计算：

状态表示：

• f[l][r][i]，表示所有将a[l...r]分割成i部分的方案的最大乘积；
• g[l][r][i]，表示所有将a[l...r]分割成i部分的方案的最小乘积；

状态计算：

首先考虑f[l][r][i]如何计算，关键是寻找“集合划分的依据”，划分依据一般选取“最后一步的操作”，所以这里我们可以按最后一部分的位置来将f[l][r][i]所表示的所有方案划分成若干类：

• 最后一段是a[l + i - 1...r]的所有划分方案；
• 最后一段是a[l + i...r]的所有划分方案;
• ...
• 最后一段是a[r...r]的所有划分方案；

如果最后一段是a[k...r]，那么这一类的最大值是 f[l][k - 1][i - 1] * sum(a[k...r])，其中sum()计算某一段数的和模10的余数。

f[l][r][i]取所有类别的最大值即可。
g[l][r][i]的计算方式类似。

最终枚举所有长度是n的区间，取最大值/最小值即可。

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10, INF = 1e9;

int n, m;
int a[N], f[N][N][M], g[N][N][M];

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

    for (int i = 1; i <= n; i ++ )
    {
        cin >> a[i];
        a[i + n] = a[i];
    }

    for (int i = 1; i <= n * 2; i ++ ) a[i] += a[i - 1];

    for (int i = 1; i <= m; i ++ )
        for (int len = i; len <= n; len ++ )
            for (int j = 1; j <= n; j ++ )
            {
                int l = j, r = j + len - 1;
                if (i == 1) f[l][r][i] = g[l][r][i] = ((a[r] - a[l - 1]) % 10 + 10) % 10;
                else
                {
                    f[l][r][i] = -INF;
                    g[l][r][i] = INF;
                    for (int k = l + i - 1; k <= r; k ++ )
                    {
                        int t = ((a[r] - a[k - 1]) % 10 + 10) % 10;
                        f[l][r][i] = max(f[l][r][i], f[l][k - 1][i - 1] * t);
                        g[l][r][i] = min(g[l][r][i], g[l][k - 1][i - 1] * t);
                    }
                }
            }

    int maxv = -INF, minv = INF;
    for (int i = 1; i <= n; i ++ )
    {
        maxv = max(maxv, f[i][i + n - 1][m]);
        minv = min(minv, g[i][i + n - 1][m]);
    }

    cout << minv << endl << maxv << endl;

    return 0;
}

2. 开心的金明

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

算法知识点: DP,背包问题

复杂度：

解题思路：

将原问题做如下转化

• 总钱数相当于背包总容量；
• 每件物品的价格相当于体积；
• 每件物品的价格乘以重要度相当于价值；

那么就变成了经典的01背包问题。

C++ 代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30010;

int n, m;
int f[N];

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

    for (int i = 0; i < n; i ++ )
    {
        int v, w;
        cin >> v >> w;
        w *= v;
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

    return 0;
}

3. 守望者的逃离

来源：NOIP2007普及组 https://ac.nowcoder.com/acm/contest/235/C

算法知识点: DP,线性DP

复杂度：

解题思路：

首先比较跑步和放技能哪个更快：

• 跑步：平均一秒 米
• 放技能：平均2.5秒恢复10点魔法，再加一秒闪烁时间，一共是3.5秒可以移动60米， 所以平均每秒 米

所以放技能稍快一些。

因此当我们有充足的放技能时间时，一定要放技能，所以只有最后一小段没时间放技能的时候，才会用跑步的方式。

然后考虑如何求解：

用f[i]表示用i的时间，最多可以跑多远。

先求出只用闪烁技能时，每秒最多可以跑多远。

再用跑步的方式来“插缝”，递推出结合两种方式时，每秒最多可以跑多远。

C++ 代码：

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

using namespace std;

const int N = 300010;

int m, s, t;
int f[N];

int main()
{
    cin >> m >> s >> t;

    for (int i = 1; i <= t; i ++ )
    {
        if (m >= 10)
        {
            f[i] = f[i - 1] + 60;
            m -= 10;
        }
        else
        {
            f[i] = f[i - 1];
            m += 4;
        }
    }

    for (int i = 1; i <= t; i ++ ) f[i] = max(f[i], f[i - 1] + 17);

    bool success = false;
    for (int i = 1; i <= t; i ++ )
        if (f[i] >= s)
        {
            printf("Yes\n%d\n", i);
            success = true;
            break;
        }
    if (!success) printf("No\n%d\n", f[t]);

    return 0;
}

4. 子矩阵

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

算法知识点: 枚举,DP,线性DP

复杂度：

解题思路：

当选定的行固定时，问题变成：

给定一个长度为 的序列，从中选出一个长度为 的子序列。序列中的每个元素均有一个分值，且任意相邻两个被选出的元素，也会产生一个分值。问：如何选择子序列可使分值之和最小。

这是一个经典的序列DP模型：

状态表示：f[i][j]表示所有以第i个数结尾，且长度为j的子序列的分值之和的最小值。

状态计算：以倒数第二个数是哪个数为依据，将f[i][j]所代表的集合分成若干类，则倒数第二个数是第k个数的所有子序列的最小分值是 f[k][j - 1] + cost()，其中cost是在序列末尾加上第i个数所产生的分值。

f[i][j]取所有类别的最小分值即可。

由于 较小，我们可以直接枚举行的所有选择，然后用上述做法DP即可。

C++ 代码：

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20, INF = 1e9;

int n, m, r, c;
int matrix[N][N];
int f[N][N];
int cw[N], rw[N][N];
int q[N];

int count(int x)
{
    int s = 0;
    for (int i = 0; i < n; i ++ ) s += x >> i & 1;
    return s;
}

int main()
{
    cin >> n >> m >> r >> c;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < m; j ++ )
            cin >> matrix[i][j];

    int res = INF;
    for (int state = 0; state < 1 << n; state ++ )
        if (count(state) == r)
        {
            for (int i = 0, j = 0; i < n; i ++ )
                if (state >> i & 1)
                    q[j ++ ] = i;

            for (int i = 0; i < m; i ++ )
            {
                cw[i] = 0;
                for (int j = 1; j < r; j ++ ) cw[i] += abs(matrix[q[j]][i] - matrix[q[j - 1]][i]);
            }

            for (int i = 0; i < m; i ++ )
                for (int j = i + 1; j < m; j ++ )
                {
                    rw[i][j] = 0;
                    for (int k = 0; k < r; k ++ )
                        rw[i][j] += abs(matrix[q[k]][i] - matrix[q[k]][j]);
                }

            for (int i = 0; i < m; i ++ )
            {
                f[i][1] = cw[i];
                for (int j = 2; j <= c; j ++ )
                {
                    f[i][j] = INF;
                    for (int k = 0; k < i; k ++ )
                        f[i][j] = min(f[i][j], f[k][j - 1] + cw[i] + rw[k][i]);
                }
                res = min(res, f[i][c]);
            }
        }

    cout << res << endl;
    return 0;
}

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