NOIP选手必备-信息学《动态规划》讲解

动态规划：参加竞赛的学生应该从竞争关系和独立关系(你做你做的，我做我做的，程序和算法彼此保密，并且每个人都喜欢谈论彼此的失败和自己的成功)转变为合作学习关系(学习任务通过相互合作的方式完成，如研究算法、集中编程、相互测量数据等)。)，2，Fibonacci序列F(n)，3，递归与动态规划，递归版本3336 F(n)1 IFN=0 orn=1 en 2 return 13 else 4 returnf(n-1)F(n-2)，动态编程3336 F(n)1a0=a1u 12 fori2 ondo 3aIu aI-1aI-24 returnn，太慢！有效！算法的复杂度为O(n)，4，方法总结，并构造了一个公式，表明问题的解是与其子问题的解相关的公式。例如，F(n)=F(n-1) F(n-2)。这些子问题被编入索引，以便它们可以更好地存储和检索到表(即数组)中，以自下而上的方式填充表；首先，填写最小子问题的解。这确保了当我们解决一个特殊的子问题时，我们可以使用比它小的所有可用子问题的解决方案。出于历史原因，我们称这种方法为动态编程。在20世纪40年代末(那时计算机很少被使用)，这些规划设计与“列表”方法有关。5.动态规划算法。算法思想是将待求解的问题分解成若干个子问题，并存储子问题的解，以避免重复子问题的计算，从子问题的解中获得原问题的解。动态规划算法通常用于解决具有某些最优性质的问题。动态规划算法的基本要素：最优子结构性质和重叠子问题。原则6，最优子结构性质：问题的最优解包含其子问题的最优解。也就是说，不管先前的策略如何，随后的决策必须是基于当前状态的最优决策(由先前的决策生成)。重叠子问题：当使用递归算法从上到下解决问题时，每次生成的子问题并不总是新问题，一些问题被重复计算。每个子问题只解决一次，然后保存解决方案，以后遇到同样的问题时可以直接引用，不需要再次解决。原理，7，动态规划，解题的基本特点，1。动态规划一般解决最大(最优、最大、最小、最长.)；通过动态规划解决的问题通常是离散的，并且可以分解(分成阶段)；3。动态规划要解决的问题必须包括最优子结构，即n的最优可以由(n-1)的最优导出。原则8。动态规划算法的四个步骤：1 .描述最优解的结构特征。(一维、二维和三维阵列)2。递归定义最优解。(状态转移方程)3。用自下而上的方法计算最优解。4.从计算出的解构造一个最优解。基本步骤、原则、9、示例、示例1。斐波那契数列F(n)，步骤1:使用F，步骤2:状态转移方程，步骤3:用自下而上的方法计算最优解，步骤4:分析和构造数组中问题的解；输入n以查找n！第一步：用F(n)代表n！的价值；第二步：状态转移方程第三步：用自下而上的方法计算最优解例11例3:排队买票，音乐会即将举行。目前有n名粉丝排队买票，每人一张，而售票处规定一次只能买两张票。假设第一个球迷需要时间t1(1In)来买票，并且队中两个相邻的球迷(第j个和第j个)也可以从其中一个球迷那里买两张票，而另一个球迷不必排队，那么两个球迷买两张票的时间就变成了Rj。如果rjf I-1 t I，则7f I f I-1 t I 8 returnf，14，示例，示例4:查找最长的非降序子序列。1.问题描述一个正整数序列：B1，B2，bn，下标i1TK(1=i=K)。你的任务是知道所有n个学生的身高，并计算需要列出的最小学生数，你可以让其余的学生组成一个合唱队。第一行输入是一个整数N(2=N=100)，表示总数第一行有n个用空格隔开的整数，第I个整数Ti(130=Tiwthen6Pi，wPi-1，w；7 else8p I，w max p I-1，w，p I-1，w-wi vi，runtime : (NW)，38，0-1背包问题的动态规划，0:n，1，w-wi，W，I-1，0，p (I，w)=max vi p (I-1，w-wi)，p (I-1，w)，带走物品I，I，W，39，p (I) 37，W，I，40，构造最优解，0，1，2，3，4，5，1，2，3，4，0，12，12，12，12，10，12，22，22，10，12，22，30，32，10，15，25，30，37，0，从P(n，W)开始向上向左时，项目I被直接取走，项目I不被取走1，0、1，10，8，6，8，10，0，6，2，8，2，8，8，6，10，0，1，6，2，3，8，2，3，8，1，6，5，10、0，0，0，0，0，0，0，0，0，0，0，0，1，1，1，1，1，1，1，1，1，1，1，1，示例3360 n=5，p=。输入格式输入格式，第一行，一个整数，表示盒子容量；第二行是一个整数，表示有n个项目；接下来的n行代表这n个项目各自的体积。OutputFormat输出格式，表示框中剩余空间的整数。样本输入，2468312797，样本输出，0，44，扩展2:草药学(vijos1104)。陈晨是一个有天赋的孩子，他的梦想是成为世界上最伟大的医生。为此，他想向附近最有声望的医生学习。为了判断他的资格，医生给他出了一道难题。医生带他到一个满是草药的山洞，对他说：“孩子，这个山洞里有一些不同的草药。收集每一个都需要一些时间，每一个都有自己的价值。我会给你一段时间，在此期间你可以收集一些草药。如果你是一个聪明的孩子，你应该能够最大限度地提高草药的总价值。”如果你是陈晨，你能完成这项任务吗？输入格式输入格式，第一行输入有两个整数T(1=T=1000)和M(1=M=100)，用空格隔开，T代表可以用来采集草药的总时间，M代表洞穴中草药的数量。接下来的M行各包含两个介于1和100之间的整数(包括1和100)，分别代表采摘某一药草的时间和药草的价值。OutputFormat包含一行，它只包含一个整数，代表在指定时间内可以采集的草药的最大总值。样本输入，7037110069112样本输出，3，45，扩展3:快乐vijos1317。金明今天很开心。他在家里买的新房子带来了钥匙。新房子有一个宽敞的房间给自己。更让他高兴的是，他的母亲昨天对他说：你有最终的决定权，只要你在你需要买什么和如何安排你的房间方面不超过n元。金明今天一大早就开始做预算，但是他想买太多的东西，这肯定会超过他妈妈的n元限额。因此，他为每个项目指定了一个重要度，并将其分为5个等级：整数15，第5级是最重要的。他还在网上找到了每种商品的价格(都是整数美元)。他希望在不超过n元(可以等于n元)的前提下，最大化每件商品的价格和重要性的乘积之和。设项目j的价格为vj，重要度为wj，选择了k个项目，编号为j1.jk，则要求的总和是：vj1*wj1.请帮助金明设计一份符合要求的购物清单。输入格式，输入行1，是两个正整数，用空格隔开：Nm(其中，N(30000)代表货币总量，m(25)代表他想购买的商品数量。)从第2行到第m 1行，第j行给出了编号为j-1的项目的基本数据。每行有两个非负整数vp(其中v代表物品的价格(v10000)，p代表物品的重要性(15)，46。OutputFormat是输出格式，输出只是一个正整数。为了达到最大价值(100000000)的产品的价格和不超过总金额的商品的重要性的总和，样品输入，100058020053005340032002，样品输出，3900，47，和扩展4:金明的预算计划(vijos1313)，金明今天非常高兴。他的家人买的新房子带来了钥匙，新房子里有一个宽敞的房间专门留给金明自己。更让他高兴的是，他的母亲昨天对他说：你有最终的决定权，只要你在你需要买什么和如何安排你的房间方面不超过n元。今天一早，金明开始做预算。他把他想买的东西分成两类：主要零件和配件。配件从属于某个主要部分。下表是一些主要零件和附件的示例：主要零件、附件、计算机打印机、扫描仪、书柜、书籍、书桌、灯具和文具椅。如果他想购买被归类为配件的物品，他必须首先购买配件所属的主要部件。每个主要零件可以有0个、1个或2个附件。附件不再有从属于它们的附件。金明想买很多东西，这肯定会超过她妈妈限定的n元。因此，他为每个项目指定了一个重要度，并将其分为5个等级：整数15，第5级是最重要的。他还在网上找到了每件商品的价格(10元的整数倍)。他希望在不超过n元(可以等于n元)的前提下，最大化每件商品的价格和重要性的乘积之和。假设项目j的价格为vj，重要性为wj，总共选择了k个项目，序列号为j1、j2，jk，那么要求的总和是：v J1 * w J1 v J2 * w J2.v JK * w JK。请帮助金明设计一份符合要求的购物清单。48，InputFormat，输入文件的第一行，是由空格分隔的两个正整数：Nm，其中N(0，表示该项目是附件，q是主要组件的序列号)，OutputFormat，输出文件只是一个正整数，它是价格与不超过总金额的项目重要性的乘积的最大值(200000)。样本输入，100058020405100403050020，样本输出，2200，49，示例9:卵石合并，描述：在圆形操场周围放置N堆卵石(N=100)，卵石将按顺序合并成一堆。规定一次只能选择两个相邻的桩合并成一个新桩，新桩中卵石的数量记录为合并的分数。编译一个程序来读取堆栈编号n和每个堆栈中鹅卵石的数量(=20)(！)选择一个合并石头的计划，用权利做n-1合并，得分之和最小；(2)选择一个合并宝石的计划。使用石头的权利必须合并n-1次，分数总和最小。输入数据：第一排碎石桩编号n；第二排每堆石头的数量由每两个数字之间的空格隔开。输出数据：是从第一行到第n行得分最低的组合方案。n-1行是空白行。n-2行到n-1行是得分最高的组合方案。每个组合方案由N行表示，其中第I行(1=i=N)表示第I行组合前每堆石头的数量(按顺时