Educational Codeforces Round 170 (Rated for Div. 2) D.Attribute Checks

Yorg / 2024-10-19 / 原文

算法

显然为 dp

状态设计

$dp_{i, j}$ 表示在第 $i$ 个获得能力点的地方, 之前智慧能力值为 $j$, 时的最大分数

状态转移

显然需要从 $dp_{i - 1, j}$ 转移而来

枚举 $j \in [0, i)$
则有(注意取 $\max$ 操作要与自己相比较)
设第 $i - 1$ 个能力点到第 $i$ 个能力点中间
$\leq k$ 的智慧检查有 $Smart_{i - 1, k}$
$\leq k$ 的力量检查有 $Power_{i - 1, k}$
则有

\[dp_{i, j} = \max{(dp_{i - 1, j})} \]

\[dp_{i, j + 1} = \max{(dp_{i - 1, j} + Smart_{i - 1, j} + Power_{i - 1, i - j - 1})} \]

\[dp_{i, j + 1} = \max{(dp_{i - 1, j + 1} + Smart_{i - 1, j + 1} + Power_{i - 1, i - j})} \]

时间复杂度

预处理 $Smart, Power$ 是 $O(m^2)$
dp 转移是 $O(m^2)$

代码

#include <bits/stdc++.h>
const int MAXN = 2e6 + 20;
const int MAXM = 5e3 + 20;

int n, m;
int r[MAXN];

int Smart[MAXM][MAXM];
int Power[MAXM][MAXM];

int dp[MAXM][MAXM];
void solve()
{
    int Ans = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            int k = i - j;
            dp[i][j] = std::max(dp[i][j], dp[i - 1][j]);
            if (j)
            {
                if (k)
                    dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + Smart[i - 1][j - 1] + Power[i - 1][k]);
                else
                    dp[i][j] = std::max(dp[i][j], dp[i - 1][j - 1] + Smart[i - 1][j - 1]);
            }
            if (k)
            {
                if (j)
                    dp[i][j] = std::max(dp[i][j], dp[i - 1][j] + Power[i - 1][k - 1] + Smart[i - 1][j]);
                else
                    dp[i][j] = std::max(dp[i][j], dp[i - 1][j] + Power[i - 1][k - 1]);
            }
            Ans = std::max(Ans, dp[i][j]);
        }
    }

    printf("%d", Ans);
}

int main()
{

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

    /*预处理*/
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if(r[i] == 0)
            cnt++;
        if(r[i] > 0)
            Smart[cnt][r[i]]++;
        if(r[i] < 0)
            Power[cnt][-r[i]]++;
    }
    if(r[n] != 0) //
        m++;

    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            Smart[j][i] += Smart[j][i - 1];
            Power[j][i] += Power[j][i - 1];
        }
    }

    /*dp*/
    solve();

    return 0;
}