题解动态规划:蓝桥杯2022国赛B组 题解 A题目

这篇具有很好参考价值的文章主要介绍了题解动态规划:蓝桥杯2022国赛B组 题解 A题目。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

在这组题(蓝桥杯C/C++ B组 国赛)里面挑了几道喜欢的题目,做了一下,笔记思路如下。(其实是我觉得能做出的题
题目图片来源于:CSDN 罚时大师月色

A:2022

【题目大意】

请问2022,拆分成10个不同的正整数有多少种不同的分法。
题解动态规划:蓝桥杯2022国赛B组 题解 A题目

【解析】

这道题目,拿到手上的时候,第一个想法是暴力,但是,每次分别枚举10位上,到底数字是多少,比如,每一位枚举从1->200,那么复杂度是 O ( 20 0 10 ) O(200^{10}) O(20010)。这个复杂度已经上天了。
但是我想应该还是有,暴力的方法,因为可以每次暴力分成两半?让我再想想这个暴力算法。

正解是,首先使用搜索,对于每一个位置进行搜索。
rec(int i,int num,int sum);
考虑第i项目(1->i项,比如题目有10位,那么我们就有10个项要填写),在当前项填入的数字为num的时候,它和前一项填入的数字有关,例如,当我们在第i项填写了num,那么前i-1项加起来,应该总和为sum-num。

举个栗子:
rec(3,5,10)=rec(2,4,10-5)+rec(2,3,10-5)+rec(2,2,10-5)+rec(2,1,10-5)
注意第二个参数,它从4,3,一直变成了1,这是在搜索,第二个位置,填入4,3…1,总和为10-5的方案数,rec(3,5,10)依赖于他们。那么,中间这个参数可以为5,或6…other 吗?不可以的,因为我们想要严格地使得,我们所搜索地数字,按照严格递增排列,所以,前一个数字,不可以大于我们当前位置上地数字。

所以,我们现在可以写出如下的代码:

typedef long long LL;
static LL dp[12][2024][2024];
int n = 2022, c = 10;
LL rec(int i, int num, int sum) {
    if (dp[i][num][sum] >= 0) {     //记忆化搜索部分
        return dp[i][num][sum];
    }

    if (i == 1 && sum != num || num <= 0 || sum <= 0) {
        return dp[i][num][sum] = 0;
    } else if (i == 1 && sum == num) {
        return dp[i][num][sum] = 1;
    }
    LL ans = 0;
    for (int j = 1; j < num; j++) {  // 在进入的时候,已经保证了,j < num,*****我们在这里循环了******
         ans += rec(i - 1, j, sum - num);
    }
    return dp[i][num][sum] = ans;
}

但是这样的算法复杂度和变量参数变化有关,为 i ∗ n u m ∗ s u m i*num*sum inumsum,然后在函数内部我们又进行了一次num的循环,所以是 i ∗ n u m ∗ s u m ∗ n u m i*num*sum*num inumsumnum,为 c ∗ n ∗ n ∗ n c*n*n*n cnnn
复杂度依旧上天。

让我们来考虑一下,还有什么地方可以被优化吗?
r e c ( 3 , 5 , 10 ) = r e c ( 2 , 4 , 10 − 5 ) + r e c ( 2 , 3 , 10 − 5 ) + r e c ( 2 , 2 , 10 − 5 ) + r e c ( 2 , 1 , 10 − 5 ) rec(3,5,10)=rec(2,4,10-5)+rec(2,3,10-5)+rec(2,2,10-5)+rec(2,1,10-5) rec(3,5,10)=rec(2,4,105)+rec(2,3,105)+rec(2,2,105)+rec(2,1,105)
之前的这个式子,观察第2项到末尾项。
即如下: r e c ( 2 , 3 , 10 − 5 ) + r e c ( 2 , 2 , 10 − 5 ) + r e c ( 2 , 1 , 10 − 5 ) rec(2,3,10-5)+rec(2,2,10-5)+rec(2,1,10-5) rec(2,3,105)+rec(2,2,105)+rec(2,1,105)
这些项目其实就是 r e c ( 3 , 5 − 1 , 10 − 1 ) rec(3,5-1,10-1) rec(3,51,101)!!!
所以,我们之前的这个:
r e c ( 3 , 5 , 10 ) = r e c ( 2 , 4 , 10 − 5 ) + r e c ( 2 , 3 , 10 − 5 ) + r e c ( 2 , 2 , 10 − 5 ) + r e c ( 2 , 1 , 10 − 5 ) rec(3,5,10)=rec(2,4,10-5)+rec(2,3,10-5)+rec(2,2,10-5)+rec(2,1,10-5) rec(3,5,10)=rec(2,4,105)+rec(2,3,105)+rec(2,2,105)+rec(2,1,105)
可以写成这个:
r e c ( 3 , 5 , 10 ) = r e c ( 2 , 4 , 10 − 5 ) + r e c ( 3 , 5 − 1 , 10 − 1 ) rec(3,5,10)=rec(2,4,10-5)+rec(3,5-1,10-1) rec(3,5,10)=rec(2,4,105)+rec(3,51,101)

我们从数学的角度尝试了简化。但是其实我们也可以从含义的角度进行简化:
对于一般的 d p [ i ] [ n u m ] [ s u m ] dp[i][num][sum] dp[i][num][sum]。我们可以有这样的考虑:
(1)魔改 d p [ i ] [ n u m − 1 ] [ s u m − 1 ] dp[i][num-1][sum-1] dp[i][num1][sum1]:对于有i项,并且第i项是num-1,总和为sum-1,所以我们可以在这个基础之上,直接把末尾的num-1变成num直接就满足我们想要的邪恶内容了,Perfect。
(2)转移 d p [ i − 1 ] [ n u m − 1 ] [ s u m − n u m ] dp[i-1][num-1][sum-num] dp[i1][num1][sumnum]:从i-1的末尾状态上,接入我们的num,这也是(1)中可能会漏掉的情况,为什么,比如我们有:
n=10 c=3
即:
1 2 7
1 3 6
1 4 5
2 3 5
末尾为5的可以从2 3 4魔改4变成5 但是无法从1 4 4把末尾4魔改成5。因为1 4 4根本不存在,所以,我们有了 d p [ i − 1 ] [ n u m − 1 ] [ s u m − n u m ] dp[i-1][num-1][sum-num] dp[i1][num1][sumnum]把num-1,sum-num,i-1接上去试一试有没有这种状态。就补足了(1)中的空缺。

LL rec(int i, int num, int sum) { 
    if (dp[i][num][sum] >= 0) {     //记忆化搜索部分
        return dp[i][num][sum];
    }

    if (i == 1 && sum != num || num <= 0 || sum <= 0) {
        return dp[i][num][sum] = 0; //num为0,不可能有成功的状态了,所以到达我们时候,num为0,直接return 0。或者i==1时候,如果填入的num,不能满足总和为sum,那么一定是错的,比如rec(1,2,3),只有一个位置,填2怎么填都不可能配出3来的
    } else if (i == 1 && sum == num) {
        return dp[i][num][sum] = 1;//i==1,并且现在填入的数字,就是我们要配出的sum总和,那么就完全O98K。
    }
    LL ans = 0;
    // for (int j = 1; j < num; j++) {  // 在进入的时候,已经保证了,j < num
    //     ans += rec(i - 1, j, sum - num);
    // }
    //如果使用For的话,那每一层都会for一次,对应DP就要多一次循环,优化思路是减少这个for
    ans += rec(i, num - 1, sum - 1);
    ans += rec(i - 1, num - 1, sum - num);
    return dp[i][num][sum] = ans;
}

我们有了记忆化搜索的思路,那么动态规划也就手到擒来了。
想想我们回溯的过程,我们从i==1开始,往i大的方向回溯。
从num小的时候,向num大的时候回溯,sum也是。

下面直接给出动态规划的代码:

#include <bits/stdc++.h>

#include <iostream>
using namespace std;
typedef long long LL;
static LL dp[12][2030][2030];
LL ans = 0;
int n = 2022, c = 10;
int main() {
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    for (int i = 1; i <= c; i++) {
        for (int num = 1; num <= n; num++) {
            for (int sum = num; sum <= n; sum++) {  //总和不可能小于所填写的数字
                dp[i][num][sum] = dp[i][num - 1][sum - 1] + dp[i - 1][num - 1][sum - num];
                if (i == c && sum == n) {  //把答案加起来
                    ans += dp[i][num][sum];
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

这段代码的意思是:

if (i == c && sum == n) {  //把答案加起来
	ans += dp[i][num][sum];
}

考虑所有的 d p [ c ] [ ∗ ] [ n ] dp[c][*][n] dp[c][][n]方案数总和,就是*为末尾数字,不停探索,符合 i = = c ∩ s u m = = n i==c \cap sum==n i==csum==n的方案。不理解,可以看看下面记忆化搜索全代码。

记忆化搜索全代码:

//这里是记忆化搜索(正确)
#include <bits/stdc++.h>

#include <iostream>
using namespace std;
typedef long long LL;
static LL dp[12][2024][2024];
int n = 2022, c = 10;
LL rec(int i, int num, int sum) {  //这修改后,去除了right(小熊写的时候,纯呼呼判断了右侧数字,但其实没必要,看下文代码)
    if (dp[i][num][sum] >= 0) {     //记忆化搜索部分
        return dp[i][num][sum];
    }

    if (i == 1 && sum != num || num <= 0 || sum <= 0) {
        return dp[i][num][sum] = 0;
    } else if (i == 1 && sum == num) {
        return dp[i][num][sum] = 1;
    }
    LL ans = 0;
    // for (int j = 1; j < num; j++) {  // 因为在进入的时候,已经保证了,j < num
    //     ans += rec(i - 1, j, sum - num);
    // }
    //如果使用For的话,那每一层都会for一次,对应DP就要多一次循环,优化思路是减少这个for
    ans += rec(i, num - 1, sum - 1);
    ans += rec(i - 1, num - 1, sum - num);
    return dp[i][num][sum] = ans;
}
int main() {
    memset(dp, -1, sizeof(dp));
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += rec(c, i, n);
    }
    cout << ans;
    return 0;
}
//rec(当前到了第i处(下标从1开始),这处填的数字,这处总和加起来是)。
//rec(i,num,sum)=res(i-1,j,sum-num)方案数; j从1到num-1,这样保证i-1处的j总是小于i处的num。
//通过观察可以发现,res(i-1,num-1,sum-num)+res(i-1,num-2,sum-num)+...+res(i-1,1,sum-num)。
//这一段,实际上就是res(i,num-1,sum-1),这样一来,就可以去除掉一个for循环,时间复杂度又降低了一个维度,使得题目可以做出。
//也可以直接从含义上理解dp[i][num][sum]=dp[i][num-1][sum-1]+dp[i-1][num-1][sum-num]
//就是,从第i项,放置数字为num,总和为sum,分为两个角度(1)直接从第i项,第i项数字为num-1,总和为sum-1的地方魔改,这样,把末尾数字+1,则可以直接满足题目的要求了。(2)从第i-1项的末尾进行拼接,我们现在状态是第i项为num,总和为sum,所以从dp[i-1][num-1][sum-num]处拼接就可以啦。num-1是要求末尾小一点,sum-num是还剩余你i-1要凑出的数字。而dp[][][]就是方案数。
//我们换种说法,比如现在我们有第i项是5,那么第i-1项如果是4,那么x x 4 5这个万一是符合答案的就会在(2)中漏掉。(1)就是为了看看我们有没有漏掉这种情况。而x x 3 4加起来等于sum-1,就不会漏掉,一个例子是n=10,c=3。则有1 4 5、2 3 5。其中2 3 5在2 3 4==9中属于(1)被加入到了答案中,而1 4 5 属于(2)的情况,被加入到了答案中。

//无论是先从i项考虑到i-1项,还是通过考虑魔改,最后答案的动态规划式都是一样的。
//从运行速度来说,记忆化搜索,和写for循环的动态规划,时间复杂度差不多,最主要在于空间复杂度。

两个写法最后答案都是对的。

——————————————————
二更

考虑10 3:
1 2 7
1 3 6
1 4 5
2 3 3
当每一位都减去1的时候
0 1 6
0 2 4
0 3 4
1 2 2
所以其实dp[3][10]=dp[3][7]+dp[2][7]
即1 2 2是dp[3][7] 而这一位减完变成开头的则是dp[2][7]
只要dp计算的是正确的(即每一位都是按照大小排列的,那么这个算法就不会有问题)
更一般的递推等式:
dp[m][n]=dp[m][n-m]+dp[m-1][n-m]

AC代码:文章来源地址https://www.toymoban.com/news/detail-404167.html

#include <bits/stdc++.h>

#include <iostream>
using namespace std;
long long dp[13][2077];
int m = 10, n = 2022;
int main() {
    memset(dp, 0, sizeof(dp));
    fill(&dp[1][1], &dp[1][2077], 1);
    for (int i = 2; i <= m; i++) {
        for (int j = 3; j <= n; j++) {
            dp[i][j] = dp[i][j - i] + dp[i - 1][j - i];
        }
    }
    cout << dp[m][n];
    return 0;
}

B:以后再写

到了这里,关于题解动态规划:蓝桥杯2022国赛B组 题解 A题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯-左移右移(2022国赛)

      小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3,… N 。   之后小蓝对这个数组进行了 M 次操作, 每次操作可能是以下 2 种之一: 左移 x , 即把 x 移动到最左边。 右移 x , 即把 x 移动到最右边。   请你回答经过 M 次操作之后, 数组从左到右每个数是多少? 输入格

    2023年04月08日
    浏览(40)
  • 十三届蓝桥杯JAVA B组国赛部分题解

    大学总共参加了三届蓝桥杯,这应该是我最后一次参加蓝桥杯了,再写一篇题解算是给自己的业余竞赛结个尾。我的题解肯定不是最好的,甚至有许多错误,能给大家提供下思路就行。 思路:模拟下时钟就行,签到题 答案:502-8=494(由于匀速运动,59分59秒到0分0秒实际算一次

    2024年02月08日
    浏览(49)
  • 十三届蓝桥杯国赛2022

    分苹果,不同之处在于一个盘子可以放0个苹果 直接贪心思想 过了90%,这种贪心其实无法保证全局最优 哪个局部没有最优呢? if(x=by=a) 这里,是选则用 A 还是用 B 我的选取规则是 尽量保留 AB 的总次数尤其是 A ,我想的是在 AB 都无法到达 9 的时候,只能用上A。但是,B也很珍

    2024年02月07日
    浏览(51)
  • 2022蓝桥杯冲刺(历年真题剖析,含省赛、国赛)

    大家好,我是莫若心,为了帮助兄弟们更好准备蓝桥杯比赛,我特意选取了蓝桥往年真题中许多能体现出蓝桥经典题型的题目,有需要的兄弟们可以收藏一下,后续我会继续更新蓝桥真题题型专栏,和大家一起冲击蓝桥杯 附上蓝桥杯官网地址:蓝桥杯官网 🚩🚩 题目如下 观

    2023年04月08日
    浏览(50)
  • 【蓝桥杯嵌入式】第十三届蓝桥杯嵌入式国赛程序设计试题以及详细题解

      本届国赛试题主要包含 LCD 、 LED 、 按键 、 EEPROM 、 串口 、 模拟电压输入 、 脉冲输入输出 七大部分,其中前面三个部分是蓝桥杯嵌入式的“亲儿子”(必考部分),而剩下的四个部分都为“干儿子”(考频相对较高)。   相对于本届省赛两套试题:   本套试题 串口数

    2024年02月02日
    浏览(90)
  • 【蓝桥杯嵌入式】第十二届蓝桥杯嵌入式国赛程序设计试题以及详细题解

      本套试题较为常规,试题主要需要使用的模块有:LCD、LED、按键、定时器输入捕获功能、采集光照传感器的值以及串口,其中最重要的是 串口收发数据 以及 定时器的输入捕获功能 ,其余的各个部分还算比较常规、比较简单。下面咱就一起来看看这届赛题的题解吧!🤤🤤

    2024年02月06日
    浏览(55)
  • 2022 RoboCom 世界机器人开发者大赛-本科组(国赛)R4,R5题解

    就是给你一堆操作修改上面的数组让他变成下面数组,输出最小修改次数和方案 一眼dp,跑一遍dp记录方案数即可; dp[i][j]表示从左往右修改,第一个数组的i位等于第二个数组的j位的最小修改方案. c++能过代码 输入样例 输出样例 思路 先lca搞出来任意两点之间的距离。然后按

    2024年02月12日
    浏览(60)
  • 第十三届蓝桥杯省赛与国赛真题题解大汇总(十四届参赛者必备)

      大家好,我是执梗。本文汇总了我写的第十三届蓝桥杯所有省赛真题与国赛真题,会针对每道题打出我自己的难度评星⭐️,也会给出每道题的算法标签,帮助大家更有针对性的去学习和准备,当然许多题目由于难度或时间的原因暂未更新,如果有不懂的问题也可以在评

    2024年02月11日
    浏览(77)
  • 2022 第十三届蓝桥杯大赛软件赛省赛(第二场),C/C++ 大学B组题解

    2022 第十三届蓝桥杯大赛软件赛省赛(第二场),C/C++ 大学B组题解 补题链接:地址 第1题 —— 练习 (5分) 题意:过了样例交上去0分,问可能是ABC的哪一种 显然都是,答案:ABC 第2题 —— 三角回文数 (5分) 题意:求第一个大于某2e8的数的回文数,且满足他可以等于1+2+…

    2023年04月09日
    浏览(56)
  • 【算法】——动态规划题目讲解

    本期继续为大家带来的是关于动态规划类题目的讲解,对于这类题目大家一定要多加练习,争取掌握。 链接如下: 62. 不同路径 题目如下: 算法思路: 1. 状态表⽰:  对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式: i. 从 [i, j] 位置出发; ii. 从起始位置出发

    2024年02月10日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包