【Codeforces】好题详解第二期 1400分动态规划（附详细代码）

用户11952558

发布于 2026-01-09 14:09:53

1360

前言 1400分即为一个分水岭，相关题目需要思维与较强代码能力，我本人也是困在这个分水岭一段时间了，并且相关题解对于新手来说很不友好，可能会用到c++17，甚至20语法，并且个人特色非常鲜明。而我都会用简洁，大家都能听懂的语言，并配上图片讲解，代码也只用C++98的语法，尽量让大家都能听懂。

此系列尽量每星期一更，希望能帮到大家

题目为我一星期做到三四十道题精心挑选的7道，都值得一做

1. Grouping Increases

连接： Problem - 1919C - Codeforces 比赛场次： Hello 2024 C

思维量： 5星 代码难度： 3星 前置知识： 无

题目大意： 一个数列，顺序不变，无损拆成2个，当前数大于后数结果+1，求结果最小值。

如：3，1，2，5，4 如果拆成3，1，2与5，4的组合，结果是1（仅1<2让结果+1）。

模型抽象 与其说将数组拆开，不如将数组分配。将num数组分配到a1,a2两个数组上，这样结果也好统计。并且结果是否++只取决于a1,a2数组的最后一个元素。

假设两个元素大的为M，小的为m,那怎么尾插数字呢？首先，m，M将数轴分为了3个区域：不会+1区（m往左），可能+1区（m~M），一定+1区（M往右）。

我们要让m，M尽量变大，并且答案尽可能不++。

x <= m 此时，就无脑将x放入m中，此时m变小，答案不会++，好事全占了。

x > M 此时，无论给m还是M都会让答案增加1。但是，当我们塞进m里后，不会+1区占比会更大，显然更利于后面操作。

x在m，M之间 有两种方案：
1. 放入m里，答案增加1，但不会+1区更宽敞
2. 放入M里，答案不会增加1，但不会+1区遭到挤压我们要看看哪个方案更优。
1. 又来了介于原m~x之间的数
此时为：（答案+1与答案不变）vs（答案不变+答案不变），第二种更优。
1. 又来了介于原x~M之间的数
此时为：（答案+1与答案+1）vs（答案不变+答案+1），都一样。因此，第二种获胜，即将x放到M中。

问题解决 因此，

x <= m放入m中
x > M放m中
其它放M中

代码分享

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;

int num[200010];
int a1[200010];
int a2[200010];
int pos1;
int pos2;

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
        a1[i] = 0;
        a2[i] = 0;
    }
    a1[0] = a2[0] = 0x3f3f3f3f;
    pos1 = 0; pos2 = 0;
    int ret = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = a1[pos1];
        int y = a2[pos2];
        int z = num[i];
        if (x < y)
        {
            if (z <= x)
            {
                a1[++pos1] = z;
            }
            else if (z > y)
            {
                a1[++pos1] = z;
                ret++;
            }
            else
            {
                a2[++pos2] = z;
            }
        }
        else
        {
            if (z <= y)
            {
                a2[++pos2] = z;
            }
            else if (z > x)
            {
                a2[++pos2] = z;
                ret++;
            }
            else
            {
                a1[++pos1] = z;
            }
        }
    }
    cout << ret << endl;
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

2. Beautiful Sequence

连接： Problem - 2069C - Codeforces 比赛场次： Educational round 174 C

思维量： 5星 代码难度： 2星 前置知识： 基础动态规划，数学归纳法

题目大意： 1，2，3三个数组组成的数组，求子序列美丽数组个数美丽数组：元素前面有值比它小,后面有值比它大的元素，首尾元素不用看两边如1，2，2，3（1比2小，3比2大）

模型抽象 首先，元素只有1，2，3，美丽子序列符合根据性质1：元素前面有值比它小 a2>a1 a3>(a1或a2)，因此a3>=a2>a1 a4>(a1或a2或a3)，因此......a4>=a3>=a2>a1 有传递性，因此a1一定是断层最小的数

同理，根据性质2：后面有值比它大 an-1<an an-2<(an-1或an) 所以an>an-1>=an-2>=an-3...... 结论，a1为1，an为3，中间为2 即1，2，......2，3为美丽子序列充要条件即找两端1，3，中间2子数组个数

题目解决 首先，我们可以暴力枚举1，3对，再用前缀数组求出中间2的个数k，再2^k-1即为此个1，3对的完美子序列个数，这里可以快速幂，但是，时间复杂度为n^2logn，会超时。

动态规划优化 首先，介绍状态机dp 我们这道题有4种状态，空数组，只有1的数组，1，2，......2数组，1，2......2，3数组其中只有最后一个是定型的，其它都可以继续生长

本题最难的部分来了！我们先模拟一下数组1，2，1，2，3（相同数字用粗体区分）先放四个区区1：只有1的数组区2：1，2，......2数组区3：1，2......2，3数组（已经定型）

先遍历数组

第一个元素：1 我们扔进区2，此时区1：（1）区2：区3：
第二个元素：2 此时区1：（1）区2：（1，2）（将区1的1和这个2组合）区3：
第三个元素：1 此时区1：（1），（1）（共有2个1，用加粗程度区分）区2：（1，2）区3：
第四个元素：2 此时，2可以加到区2的（1，2）后面区1：（1），（1）区2：（1，2），（1，2，2）区3：此外，2可以加到区1的所有数组后面区1：（1），（1）区2：（1，2），（1，2，2）（1，2），（1，2）区3：总结，2可以加到区2，区1的所有数组后面
第五个元素：3 3只能加到区2的数组后面此时区1：（1），（1）区2：（1，2），（1，2，2）（1，2），（1，2）区3：（1，2，3），（1，2，2，3）（1，2，3），（1，2，3）因此，答案就是4个

我们设三种状态分别为dp[1],dp[2],dp[3] 方法总结：遍历数组，1就是dp[1]++ 2由于能接到区域2，区域1上面，因此dp[2]=dp[2]*2+dp[1] 3只能接到区3后面，因此dp[3]=dp[2]+dp[3] 由于只有区3是定型的，因此最后答案就是dp[3]的值

代码分享

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;

int num[200010];
const int mod = 998244353;

int add(int a, int b)
{
    return (a + b) % mod;
}

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
    }
    int dp[4] = { 0 };
    dp[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (num[i] == 2)
        {
            dp[2] = add(dp[2], dp[2]);
        }
        dp[num[i]] = add(dp[num[i] - 1], dp[num[i]]);
    }
    cout << dp[3] << endl;
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

3. Sakurako‘s Field Trip

连接： Problem - 2033C - Codeforces 比赛场次： Round 981 div3 C

思维量： 3星 代码难度： 2星 难题做多了，弄点简单的休息一下 前置知识： 基础动态规划

题目大意： 能否通过不限次数的轴对称交换（换第 i ， n−i+1个元素）使得相邻数字相等最少？回答最小值

题目样例分析 2 1 1 2 2 4 从中间的1，2开始，向两边扩散，两边是1，2，只用旋转为2，1就可以与中间不同再向两边扩散较中间元素为1，2，两边元素为2，4 两种情况 2，1中间数字2，4和4，1中间数字2，2 显然第一种更优

模型抽象 我们只用从中间往两边扩，判断答案最少会因为这一层加几即可

代码分享

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
#include<random>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
using namespace std;

int num[200010];
int dp[200010];

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
        dp[i] = 0;
    }
    int k = (n+1) / 2;
    int l = 0; int r = 0;
    int ret = 0;
    if (n % 2 == 1)
    {
        r=l = n / 2 + 1;
       
    }
    else
    {
        l = n / 2;
        r = n / 2 + 1;
        if (num[l] == num[r])ret++;
    }
    for (int i = 1; i <= (n-1)/2; i++)
    {
        int c = min((num[l - 1] == num[l] ? 1 : 0) + (num[r + 1] == num[r] ? 1 : 0), (num[l - 1] == num[r] ? 1 : 0) + (num[r + 1] == num[l] ? 1 : 0));
        dp[i + 1] = dp[i] + c;
        l--; r++;
    }
    cout << dp[(n + 1) / 2]+ret << endl;
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

4. Maximize the Root

连接： Problem - 1997D - Codeforces 比赛场次： Educational round 168 D

思维量： 4星 代码难度： 4星

题目大意： 二叉树，1号节点为根，进行不限次操作，节点+1，节点下面所有子节点-1，所有节点不能变为负数，问1号根节点最后最大值

题目用例分析

0------1 0------1 1------0 | | | 0 -> 1 -> 0 | | | 2 1 0

2------3------5------6------9 ->5------0------2------3------6 ->5------1------1------2------5 ->6------0------0------1------4

模型抽象 由此我们现总结规律：

得到的结果一定大于等于根节点+最小的子节点如2------3------5------6------9，根节点为2，最小子节点为3，结果一定>=5（即后面都减去3）
如果一个节点要增大a，那么数列一定要有把后一个元素变为2*a的实力如5------0------2------3------6，根节点值要增加1，那么就要有先要把第二个节点变为1的实力 5------1------1------2------5，再将根节点增加1：6------0------0------1------4 再举个例子 5------0------0------4，要让5这个节点增加1，那么数列就要有能把2号节点变为2的实力，但是2现在小于2 那么数列就先要有能把3号节点变为4的实力，一看4号节点为4，够了，因此1号节点就能+1

因此，这道题本质上就是在试错的过程： 1号节点可以+10吗？------不行那可以+1吗？------可以那可以+5吗？------可以那可以+7吗？------不行............ 那这不就是二分查找吗

我们先用送给check函数一个值k，看看是否根节点具有+k的实力判断规则，即为

如果子节点>=k,那么没有欠债，只需要保持子节点都>=k即可（对应规律1）
如果子节点欠债了，那么就需要孙子节点有还债的实力------即后面二叉树是否具有把子节点变为2k的实力，去还债，即孙子节点是否有（2k-子节点）的大小

拿什么时候定音呢

债务过大（超过1e9，即题目的最大值）时，return false
都能还上，return true

代码分享

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);

int num[200010];
vector<int> tu[200010];

bool check(int ro, int s)
{
    if (s > 1e9 + 10)return false;
    ////if (ro == 1 && num[ro] >= s)return 1;
    if (tu[ro].size() == 0)
    {
        return num[ro] >= s;
    }
    if (s <= num[ro])
    {
        for (int i = 0; i < tu[ro].size(); i++)
        {
            if (!check(tu[ro][i], s))return false;
        }
    }
    else
    {
        for (int i = 0; i < tu[ro].size(); i++)
        {
            int p = 2 * s - num[ro];
            if (!check(tu[ro][i], p))return false;
        }
    }
    return 1;
}
bool _check(int s)
{
    for (int i = 0; i < tu[1].size(); i++)
    {
        int p = tu[1][i];
        if (!check(p, s))return 0;
    }
    return 1;
}

void solve()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
        tu[i].clear();
    }
    for (int i = 1; i < n; i++)
    {
        int a; cin >> a;
        tu[a].push_back(i + 1);
    }
    int l = 0; int r = 1e9 + 5;
    while (l < r)
    {
        int m = (l + r + 1) / 2;
        if (_check(m)) l = m;
        else r = m - 1;
    }
    cout << num[1] + l << endl;
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

5. Did We Get Everything Covered?

连接： Problem - 1924A - Codeforces 比赛场次： Round 921 div1 A

思维量： 3星 代码难度： 2星

题目大意： 字符串中，是否能挑出m个字符长度的子串，可以涵盖字母表前k个字母长度为m的排列？不行的话输出哪个不行

题目用例讲解 2 2 4 abba K=2，m=2 字母表前2个字母为a，b 长为m（2）的所有排列为：aa,ab,ba,bb 这些都有，因此可以

3 3 10 aabbccabab K=3,m=3 字母表前3个字母为a，b，c 长为m（3）的所有排列为：aaa,bbb,ccc,aab...... 没有ccc，不行，输出ccc即可

模型抽象 我们先取m=3，k=3，看看什么字符串满足要求首先，abcabcabc是满足要求的，因为可以先从第一组abc里取出a/b/c，再从第二组abc里取出a/b/c...... 因此，猜想：是否有m组完整的k个字母组就可行？

显然m组k字母循环是一定可行的，那它是不是最优呢

假设每个abc组的最后一个字母都是c，那么abc组前面就是a，b两个字母那我们ccc这个排列时，就要组一最后一个c搭配组二最后一个c搭配组三最后一个c 恰好是最极限的情况因此，理论上是最优解的

怎么找反例？由上文，我们可知只需要用最极限的用例为难它即为将每一个组的最后一个元素给放出来，直到最后一组，选没有的字符比如 aabbccabab 分组 aabbc|||cab|||ab 第一组，第二组abc齐全，但第三组缺c，因此反例最后一个元素为c 其他组选最后一个，即为c，b，c 显然是不含这个子数组的

代码分享

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);

void solve()
{
    int n; int k; int m;
    cin >> n >> k >> m;
    string s; cin >> s;
    s = " " + s;
    int tmp[30] = { 0 };
    int cnt = 0;
    int c = 0;
    string ret;
    for (int i = 1; i <= m; i++)
    {
        if (tmp[s[i] - 'a'] == 0)
        {
            cnt++;
            tmp[s[i] - 'a']++;
        }
        if (cnt == k)
        {
            cnt = 0;
            c++;
            for (int i = 0; i <= 29; i++)
            {
                tmp[i] = 0;
            }
            ret += s[i];
        }
    }
    if (ret.size() < n)
    {
        for (int i = 0; i < k; i++)
        {
            if (tmp[i] == 0)
            {
                ret += ('a' + i);
                break;
            }
        }
    }
    while (ret.size() < n)
    {
        ret += 'a';
    }
    if (c < n)
    {
        cout << "NO" << endl;
        cout << ret << endl;
    }
    else
    {
        cout << "YES" << endl;
    }
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

6. Needle in a Haystack

连接： Problem - C - Codeforces 比赛场次： Round 1069 div2

思维量： 4星 代码难度： 2星

题目大意： 将字符串t重新排列，使字符串s为子串情况下字典序最小

题目用例解析： S:dcbe T:bedbaecfc 首先，结果里一定要有d c b e这个顺序的字符排列，就相当于将t剩下的字符重新排列，插入s中因此，就变成了dcbe，abcef如何排列字典序最小

模型抽象 显然，哪个字符小就放哪个到第一位因此，就为a b c d c e e f

但是，如果有相同的字符呢不要忽略一个条件，t剩下的字符是重新排列过的，因此后面的字母一定>=前面字母但是s没排列过，因此后面字符可能小于前面的，先排s的字符只会更容易遇到小的字母降低字典序

如cb，cd 在排到c后，如果先排s，结果是cbcd，先t，结果为ccbd，结果前面小，就是因为先遇到了小的字符，先进入排列，让结果更小

代码分享

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);

void solve()
{
    string a; string b;
    cin >> a >> b;
    int tmp[30] = { 0 };
    for (int i = 0; i < b.size(); i++)
    {
        tmp[b[i] - 'a']++;
    }
    for (int i = 0; i < a.size(); i++)
    {
        tmp[a[i] - 'a']--;
        if (tmp[a[i] - 'a'] < 0)
        {
            cout << "Impossible" << endl;
            return;
        }
    }
    string p;
    for (int i = 0; i < 26; i++)
    {
        for (int j = 1; j <= tmp[i]; j++)
        {
            p += ('a' + i);
        }
    }
    int c1 = 0; int c2 = 0;
    string ret;
    while (c1 < a.size() && c2 < p.size())
    {
        if (a[c1] <= p[c2])
        {
            ret += (a[c1++]);
        }
        else
        {
            ret += p[c2++];
        }
    }
    while (c1 < a.size())
    {
        ret += a[c1++];
    }
    while (c2 < p.size())
    {
        ret += p[c2++];
    }
    cout << ret << endl;
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

7. Dungeon

连接： Problem - 2164C - Codeforces 比赛场次： Global round 30 div2 c

思维量： 3星 代码难度： 4星 前置知识： set，multi-set的使用

题目大意： 有剑（伤害ai），怪物（血量bi，ci不为0就死后掉装备，掉max(ai,ci)），问能杀多少怪

题目用例分析 a:1,7,7(伤害) b：2 ,2,2,6,6（怪物血量） c：7,2,0,2,0（掉装备）首先，先用7伤害的剑杀（2，7）的怪，掉7，先用7伤害的剑杀（2，2）的怪，掉7，先用7伤害的剑杀（6，2）的怪，掉7，再将c为0的怪一网打尽

模型抽象 由此，我们知道，打c不为0的怪就是装备升级游戏，只可能装备变好但是打c为0的怪就会装备降级，因为它不会掉剑

结论1：为了尽可能多打怪，先打c不为0的结论2：我们打血量为2的怪，只会拿伤害3的剑，不会拿伤害为4的在打升级系的怪时，由于我们只可能升级，因此先从小怪开始，用他们可能得到的更强力装备去打大怪结论3：先小怪后大怪

题目解决 为了快速找到可以击杀怪的最小剑，我们弄一个multi-set维护，以快速查找最适合的剑（由于set会自动去掉重复的，因此用multi-set），再遍历ci不为0的怪，升级装备最后才去打c=0的怪

代码分享

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include <cstring>
#include<cmath>
#include<queue>
#include <deque>
#include <stack>
#include<iomanip>
#include <chrono>
using namespace std;
//typedef __int128 ll;
typedef long long ll;
typedef unsigned long long ull;
#define int long long
#define y2 my_y2
#define y1 my_y1
typedef pair<int, int> PII;
//ios::sync_with_stdio(false);
//cin.tie(nullptr);

int num[200010];
struct node
{
    int bl;
    int ge;
}sow[200010], zeo[200010],nzeo[200010];
int pos;
int pos2;

bool cmp2(node& a, node& b)
{
    if(a.bl!=b.bl)
        return a.bl < b.bl;
    return a.ge < b.ge;
}

void solve()
{
    int n; cin >> n;
    int k; cin >> k;
    multiset<int> se;
    pos = pos2 = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
        se.insert(num[i]);
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> sow[i].bl;
    }
    for (int i = 1; i <= k; i++)
    {
        cin >> sow[i].ge;
    }
    int ret = 0;
    //priority_queue<int, vector<int>, cmp> heap;
    sort(num + 1, num + n + 1);
    sort(sow + 1, sow + 1 + k, cmp2);
    for (int i = 1; i <= k; i++)
    {
        if (sow[i].ge == 0)
        {
            nzeo[++pos2].bl = sow[i].bl;
            nzeo[pos2].ge = sow[i].ge;
        }
        else
        {
            zeo[++pos].bl = sow[i].bl;
            zeo[pos].ge = sow[i].ge;
        }
    }
    for (int i = 1; i <= pos; i++)
    {
        auto it = se.lower_bound(zeo[i].bl);
        //--it;
        int t = *it;
        if (it == se.end())
        {
            continue;
        }
        se.erase(it);
        ret++;
        se.insert(max(t,zeo[i].ge));
    }
    for (int i = 1; i <= pos2; i++)
    {
        auto it = se.lower_bound(nzeo[i].bl);
        if (it == se.end())
        {
            continue;
        }
        se.erase(it);
        ret++;
    }
    cout << ret << endl;
}

signed main()
{
    int t; cin >> t;
    while (t--)solve();
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2026-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除

动态规划