2019牛客暑期NOIP真题班提高组9-DP2

1. 矩阵取数游戏

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

算法知识点: 区间DP，高精度

复杂度：

解题思路：

状态表示： 表示将 [i, j] 这段数取完的所有取法的最大分值。

状态计算：将 所表示的所有取法分成两类：

• 先取左端点。这一类的最大分值是 ，其中 是第 个数的值。
• 先取右端点。这一类的最大分值是 ，其中 是第 个数的值。

则 就是这两类的较大值。

C++ 代码：

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

typedef long long LL;
typedef vector<int> VI; const int N = 90;

int n, m;
int g[N];
VI f[N][N];
VI power2[N];

VI add(VI a, VI b)
{
    static VI c;
    c.clear();
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++)
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 100000000);
        t /= 100000000;
    }
    return c;
}

VI mul(VI A, int b)
{
    static VI C;
    C.clear();
    LL t = 0;
    for (int i = 0; i < A.size() || t; i++)
    {
        if (i < A.size()) t += (LL) A[i] *b;
        C.push_back(t % 100000000);
        t /= 100000000;
    }
    return C;
}

VI maxV(VI A, VI B)
{
    if (A.size() != B.size())
    {
        if (A.size() > B.size()) return A;
        return B;
    }
    for (int i = A.size() - 1; i >= 0; i--)
    {
        if (A[i] > B[i]) return A;
        if (A[i] < B[i]) return B;
    }
    return A;
}

void print(VI A)
{
    printf("%d", A.back());
    for (int i = A.size() - 2; i >= 0; i--) printf("%08d", A[i]);
    puts("");
}

VI work()
{
    for (int len = 1; len <= m; len++)
        for (int l = 1; l + len - 1 <= m; l++)
        {
            int r = l + len - 1;
            if (l == r) f[l][r] = mul(power2[m - len + 1], g[r]);
            else
            {
                auto left = add(mul(power2[m - len + 1], g[l]), f[l + 1][r]);
                auto right = add(mul(power2[m - len + 1], g[r]), f[l][r - 1]);
                f[l][r] = maxV(left, right);
            }
        }

    return f[1][m];
}

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

    power2[0] = { 1 };
    for (int i = 1; i <= m; i++) power2[i] = mul(power2[i - 1], 2);

    VI res(1, 0);
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j <= m; j++) scanf("%d", &g[j]);
        res = add(res, work());
    }

    print(res);

    return 0;
}

2. 传纸条

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

算法知识点: 线性DP

复杂度：

解题思路：

状态表示：f[k, i, j] 表示两个人同时走了k步，第一个人在 (i, k - i) 处，第二个人在 (j, k - j)处的所有走法的最大分值。

状态计算：按照最后一步两个人的走法分成四种情况：

• 两个人同时向右走，最大分值是 f[k - 1, i, j] + score(k, i, j)；
• 第一个人向右走，第二个人向下走，最大分值是 f[k - 1, i, j - 1] + score(k, i, j)；
• 第一个人向下走，第二个人向右走，最大分值是 f[k - 1, i - 1, j] + score(k, i, j)；
• 两个人同时向下走，最大分值是 f[k - 1, i - 1, j - 1] + score(k, i, j)；

其中如果两人在相同格子，则 score(k, i, j) 等于这个格子的分值；否则等于两个格子的分值之和。

C++ 代码：

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

int n, m;
int g[N][N];
int f[N * 2][N][N];

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

    for (int k = 2; k <= n + m; k++)
        for (int i = max(1, k - m); i <= n && i < k; i++)
            for (int j = max(1, k - m); j <= n && j < k; j++)
                for (int a = 0; a <= 1; a++)
                    for (int b = 0; b <= 1; b++)
                    {
                        int t = g[i][k - i];
                        if (i != j) t += g[j][k - j];
                        f[k][i][j] = max(f[k][i][j], f[k - 1][i - a][j - b] + t);
                    }

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

    return 0;
}

3. 乌龟棋

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

算法知识点: 线性DP

复杂度：

解题思路：

状态表示： 表示所有第 种卡片使用了 张的走法的最大分值。

状态计算：将 表示的所有走法按最后一步选择哪张卡片分成四类：第 类为最后一步选择第 种卡片。比如 ，则这一类的最大分值是 。

C++ 代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 360,
    M = 41;

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

int main()
{
    int b[5] = { 0 };
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &score[i]);

    for (int i = 0; i < m; i++)
    {
        int t;
        scanf("%d", &t);
        b[t]++;
    }

    for (int A = 0; A <= b[1]; A++)
        for (int B = 0; B <= b[2]; B++)
            for (int C = 0; C <= b[3]; C++)
                for (int D = 0; D <= b[4]; D++)
                {
                    int t = score[A + B * 2 + C * 3 + D * 4];
                    int &v = f[A][B][C][D];
                    v = t;
                    if (A) v = max(v, f[A - 1][B][C][D] + t);
                    if (B) v = max(v, f[A][B - 1][C][D] + t);
                    if (C) v = max(v, f[A][B][C - 1][D] + t);
                    if (D) v = max(v, f[A][B][C][D - 1] + t);
                }

    printf("%d\n", f[b[1]][b[2]][b[3]][b[4]]);
    return 0;
}

4. 子串

来源：NOIP2015提高组

算法知识点: 线性DP，前缀和

复杂度：

解题思路：

状态表示：f[i, j, k]表示只用S的前i个字母，选取了k段，可以匹配T的前j个字母的方案数。

状态计算：将f[i, j, k]表示的所有方案分成两大类：

1. 不用S[i]，则方案数是 f[i - 1, j, k]；
2. 使用S[i]，那么可以按S[i]所在的一段一共有多少字母继续分类：
   • 如果有t个字母，则方案数是f[i - t, j - t, k - 1]

所以f[i, j, k] = f[i - 1, j, k] + sum(f[i - t, j - t, k - 1])。
其中t只要满足S[i - t + 1] == T[j - t + 1]就可以一直往前枚举，因此最坏情况下的时间复杂度是 ，会超时。

接下来考虑如何优化。

我们发现f[i, j, k]第二项的表达式和f[i - 1, j - 1, k]第二项的表达式很像，具有递推关系，因此可以令sum[i, j, k] = sum(f[i - t, j - t, k])，则：

• 如果 S[i] == T[j]，那么 sum[i, j, k] = sum[i - 1, j - 1, k] + f[i - 1, j - 1, k - 1]；
• 如果 S[i] != T[j]，那么 sum[i, j, k] = 0；

至此，时间复杂度可以降至 。

C++ 代码：

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

int n, m, K;
char S[N], T[N];
int f[N][N], sum[N][N];

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

    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = m; j; j--)
            for (int k = K; k; k--)
            {
                if (S[i] == T[j]) sum[j][k] = sum[j - 1][k] + f[j - 1][k - 1];
                f[j][k] += sum[j][k];
            }

    printf("%d\n", f[m][K]);
    return 0;
}

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