自驾游网站模板,中铁建设集团北京工程有限公司,wordpress修改ip,有FTP免费网站信息学奥赛一本通#xff08;C版#xff09;在线评测系统 基础算法 第一节 动态规划的基本模型 1285#xff1a;最大上升子序列和 “最大上升子序列和”问题课堂讲解
1. 理解题意
同学们#xff0c;想象我们有一串数字#xff0c;就像一串彩色的珠子#xff0c;每个珠子…信息学奥赛一本通C版在线评测系统 基础算法 第一节 动态规划的基本模型 1285最大上升子序列和 “最大上升子序列和”问题课堂讲解
1. 理解题意
同学们想象我们有一串数字就像一串彩色的珠子每个珠子上都标着一个数字这就是题目里说的序列。比如有这样一串数字(1)(7)(3)(5)(9)(4)(8)。
现在我们要从这串数字里挑出一些数字这些数字要满足后面的数字比前面的数字大这样挑出来的数字组成的新序列就叫上升子序列。比如说从上面那串数字里挑出(1)(3)(5)(9)这就是一个上升子序列。
我们的任务是在所有能挑出来的上升子序列里找到数字加起来和最大的那个上升子序列然后把这个最大的和告诉大家。要注意哦最长的上升子序列它的数字和不一定是最大的。就像数字序列(100)(1)(2)(3)最长的上升子序列是(1)(2)(3)但是数字和最大的上升子序列是(100)因为(100)比(1 2 3)的和要大。
2. 解题思路
我们可以用一种像搭积木一样的方法来解决这个问题这种方法叫动态规划。
我们先给每个数字都想象有一个“小背包”这个“小背包”里装着以这个数字结尾的最大上升子序列的和。一开始每个数字自己就是一个长度为(1)的上升子序列所以每个数字“小背包”里的和就是它自己的值。
然后呢我们从第二个数字开始一个一个地看。对于每个数字我们回头看看它前面的那些数字。要是前面有个数字比它小那就说明可以把这个小的数字和当前数字连起来形成一个新的上升子序列。我们就把前面那个小数字“小背包”里的和加上当前数字得到一个新的和。我们比较一下是原来这个数字“小背包”里的和大还是新得到的和大把大的那个存到当前数字的“小背包”里。
最后我们看看所有数字的“小背包”找出里面最大的那个和这个和就是我们要找的最大上升子序列的和啦。
3. 解题步骤
输入数字序列我们要先知道这串数字有多少个也就是输入序列的长度(N)。然后把这串数字里的每个数字都一个一个地记下来存到一个数组里。初始化“小背包”让每个数字的“小背包”也就是存储以该数字结尾的最大上升子序列和的数组里都先装上它自己的值因为每个数字自己就是长度为(1)的上升子序列和就是它本身。更新“小背包”从第二个数字开始一个一个地看对于每个数字看看它前面比它小的数字把前面小数字“小背包”里的和加上当前数字和原来当前数字“小背包”里的和比较把大的那个存到当前数字的“小背包”里。找出最大和看看所有数字的“小背包”找出里面最大的那个和这就是我们要的答案。
4. C代码实现
#include iostream // 包含输入输出流的头文件这样我们就能从键盘输入数字把结果输出到屏幕上啦
using namespace std; int main() {int n; // 定义一个变量 n用来存数字序列里有多少个数字cin n; // 从键盘输入数字的个数存到 n 里int a[1005]; // 定义一个数组 a用来存数字序列最多能存 1005 个数字int dp[1005]; // 定义一个数组 dp这就是我们说的“小背包”数组用来存以每个数字结尾的最大上升子序列的和// 输入数字序列并初始化“小背包”for (int i 1; i n; i) {cin a[i]; // 从键盘输入一个数字存到数组 a 的第 i 个位置dp[i] a[i]; // 把“小背包”数组 dp 的第 i 个位置初始化为当前数字 a[i]}// 更新“小背包”for (int i 2; i n; i) { // 从第二个数字开始看for (int j 1; j i; j) { // 看看当前数字前面的所有数字if (a[j] a[i]) { // 如果前面的数字 a[j] 比当前数字 a[i] 小// 比较 dp[i] 和 dp[j] a[i] 的大小把大的那个存到 dp[i] 里dp[i] max(dp[i], dp[j] a[i]); }}}int ans 0; // 定义一个变量 ans用来存最大上升子序列的和先初始化为 0// 找出“小背包”数组里的最大值for (int i 1; i n; i) {ans max(ans, dp[i]); // 比较 ans 和 dp[i] 的大小把大的那个存到 ans 里}cout ans endl; // 把最大上升子序列的和输出到屏幕上return 0;
}5. 知识点总结
数组我们用了两个数组(a)数组存原始的数字序列(dp)数组存每个数字对应的“小背包”里的和。数组就像一个小抽屉我们可以把很多东西这里是数字一个一个地放进去还能按照顺序找到它们。循环循环就像一个勤劳的小工人会按照我们的要求重复做一些事情。这里用了两层循环外层循环一个一个地看数字内层循环回头看前面的数字这样就能更新每个数字的“小背包”啦。动态规划这是一种很厉害的解题方法把大问题分成很多小问题先解决小问题再从这些小问题的答案里找到大问题的答案。在这个问题里我们先算出每个数字对应的最大上升子序列的和再从这些和里找出最大的就是整个序列的最大上升子序列的和啦。比较大小用(max)函数来比较两个数的大小找出大的那个数。这样就能更新“小背包”里的和以及最终的最大和答案啦。
