dp泛做1_现有个物品,第个物品有两个属性和。在其中选取若干个物品,使最大,同时,均非负(表-程序员宅基地

技术标签: dp  

这里的dp范做根据网上的动态归法分析和网上的有个100个dp方程做的,题解很多是原版,没怎么动,有些是别人的一些其他做法,还有一些自己的想法。如果看到题解很别人一样,那就是摘自别人的。且这里只是一半。

由于本文有些摘自网上,如有原主看到不想在此贴出的,请说明,将会撤出。

如此文方法错误,或者冒犯某些原博主的文章还请见谅,还请指出,非常感谢

机器分配(HNOI’95)

0-1背包变形tyvj1089smrtfun

最长不下降序列(HNOI’97)

石子合并(NOI’95)

凸多边形三角划分(HNOI’97)

乘积最大(noip’2000)

系统可靠性(HNOI’98)

过河(noip’2005)

加分二叉树(noip’2003)

选课(CTSC’98)

砝码称重(noip’96)

核电站问题

数的划分(noip2001)

最大01矩阵

最大子矩阵(Scoi’05)

加+-被k整除(poj1745)

方块消除(poj1390)

装箱问题(noip2001)

数字三角形

晴天小猪历险记同一阶段上暴力动态规划

小胖办证(双向动态规划1,数字三角形)

马拦卒过河noip2002

打砖块(tyvj’1505)

打鼹鼠(CscIIvijos1441)

贪吃的九头龙(NOI2002)

状态压缩dp炮兵阵地(poj1185)

常用递推式子

排列组合中的环形染色问题

隐形的翅膀-线性搜索

陨石的秘密(NOI’2001)

合唱队形(noi2004)

今明的预算方案(noip2006)

花店橱窗布置(IOI’99)

化工厂装箱员

欢乐的聚会spfa+dp

小胖守皇宫(treedp)

活动安排(xtu2012)

有向树k中值问题

CEOI1998 Substract

古城之谜(Noi2000)

单词的划分(tyvj1102)

统计单词个数(Noip2001)

括号序列—tyvj1193

括号序列poj1141

棋盘分割(NOI’99,poj1191)

聪聪和可可(noi2005)

血缘关系

决斗(rqnoj458)

跳舞家怀特先生(tyvj1211)

积木游戏(NOI’97)

逃学的小孩(NOI2003)


机器分配(HNOI’95

一、问题描述

总公司拥有高效生产设备M台,准备分给下属的N个公司。各分公司若获得这些设备,可以为国家提供一定的盈利。问:如何分配这M台设备才能使国家得到的盈利最大?求出最大盈利值。其中M《=15,N〈=10。分配原则:每个公司有权获得任意数目的设备,但总台数不得超过总设备数M。保存数据的文件名从键盘输入。

数据文件格式为:第一行保存两个数,第一个数是设备台数M,第二个数是分公司数N。接下来是一个M*N的矩阵,表明了第I个公司分配J台机器的盈利。

二、分析

     这是一个典型的动态规划试题。用机器数来做状态,数组F[I,J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为

F[I,J]=Max{F[I-1,K] + Value[I,J-K]} (0〈=K〈=J〉

0-1背包变形tyvj1089smrtfun

一、问题描述

现有N个物品,第i个物品有两个属性A_i和B_i。在其中选取若干个物品,使得sum{A_i + B_i}最大,同时sum{A_i},sum{B_i}均非负(sum{}表示求和)。

输入:第一行,一个整数,表示物品个数N。 接下来N行,每行两个整数,表示A_i和B_i。

输出:一个整数,表示最大的sum{A_i + B_i}。

 N <= 100 , |A_i| <= 1000 , |B_i| <= 1000

二、分析

首先就是表示状态 f[i]表示当sum{b}为i时sum{a}的最大值,那么sum{b}就相当于背包的体积(可以为负),b[i]就相当于物品的体积(但可以为负值),那没有一个确定的背包体积怎么办呢。。就在线的扩展MAX,初始化MAX=0;比如说第一个b[i];放进去的时候就扩展一下MAX+=b[i];把Ai的和当背包的重量,把Bi的和当成价值来做,每次重量考察Ai和的最小到最大

对于f[]的上限注意了,可不是经典的零。。因为体积(sum{b[i]})可以为负所以就要设置一个MIN来表示其上限。不断地更新MIN,类似MAX那样更新。

最后把j从0到MAX枚举一下

对于当w[i]<0的时候为什么要把for循环那个MIN to MAX+w[i]而不是AX to MIN+w[i];疑问:MIN to MAX+w[i]不就是放无数次,成为完全背包了吗?答:因为w[i]<0.

f[j]:=max(f[j], f[j-a[i]]+b[i])

最长不下降序列(HNOI’97

一、问题描述

设有整数序列b1,b2,b3,…,bm,若存在i1<i2<i3<…<in,且bi1<bi2<bi3<…<bin,则称 b1,b2,b3,…,bm中有长度为n的不下降序列bi1,bi2,bi3,…,bin。求序列b1,b2,b3,…,bm中所有长度(n)最大不下降子序列

输入:整数序列

输出:最大长度n和所有长度为n的序列个数Total

二、分析

LIS(Longest Increasing Subsequence)最长上升(不下降)子序列,有两种算法复杂度为O(n*logn)和O(n^2)。在上述算法中,若使用朴素的顺序查找在D1..Dlen查找,由于共有O(n)个元素需要计算,每次计算时的复杂度是O(n),则整个算法的时间复杂度为O(n^2),与原来算法相比没有任何进步。但是由于D的特点(2),在D中查找时,可以使用二分查找高效地完成,则整个算法时间复杂度下降为O(nlogn),有了非常显著的提高。需要注意的是,D在算法结束后记录的并不是一个符合题意的最长上升子序列!算法还可以扩展到整个最长子序列系列问题。有两种算法复杂度为O(n*logn)和O(n^2)
O(n^2)算法分析如下

(a[1]...a[n] 存的都是输入的数)
  1、对于a[n]来说,由于它是最后一个数,所以当从a[n]开始查找时,只存在长度为1的不下降子序列;

2、若从a[n-1]开始查找,则存在下面的两种可能性:

(1)若a[n-1] < a[n] 则存在长度为2的不下降子序列 a[n-1],a[n].

(2)若a[n-1] > a[n] 则存在长度为1的不下降子序列 a[n-1]或者a[n]。

3、一般若从a[t]开始,此时最长不下降子序列应该是按下列方法求出的:

在a[t+1],a[t+2],...a[n]中,找出一个比a[t]大的且最长的不下降子序列,作为它的后继。

4、为算法上的需要,定义一个数组:

d:array [1..n,1..3] of integer;

d[t,1]表示a[t]

d[t,2]表示从i位置到达n的最长不下降子序列的长度

d[t,3]表示从i位置开始最长不下降子序列的下一个位置

最长不下降子序列的O(n*logn)算法

先回顾经典的O(n^2)的动态规划算法,设A[t]表示序列中的第t个数,F[t]表示从1到t这一段中以t结尾的最长上升子序列的长度,初始时设F[t] = 0(t = 1, 2,..., len(A))。则有动态规划方程:F[t]= max{1, F[j] + 1} (j = 1, 2, ..., t - 1, 且A[j] < A[t])。

现在,我们仔细考虑计算F[t]时的情况。假设有两个元素A[x]和A[y],满足

(1)x < y < t (2)A[x] < A[y] < A[t] (3)F[x] =F[y]

此时,选择F[x]和选择F[y]都可以得到同样的F[t]值,那么,在最长上升子序列的这个位置中,应该选择A[x]还是应该选择A[y]呢?

很明显,选择A[x]比选择A[y]要好。因为由于条件(2),在A[x+1] ... A[t-1]这一段中,如果存在A[z],A[x] < A[z] < a[y],则与选择A[y]相比,将会得到更长的上升子序列。

再根据条件(3),我们会得到一个启示:根据F[]的值进行分类。对于F[]的每一个取值k,我们只需要保留满足F[t] = k的所有A[t]中的最小值。设D[k]记录这个值,即D[k] = min{A[t]} (F[t] = k)。

注意到D[]的两个特点:

(1) D[k]的值是在整个计算过程中是单调不上升的。

(2) D[]的值是有序的,即D[1]< D[2] < D[3] < ... < D[n]。

利用D[],我们可以得到另外一种计算最长上升子序列长度的方法。设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A[t] > D[len],则将A[t]接在D[len]后将得到一个更长的上升子序列,len = len + 1, D[len] = A[t];否则,在D[1]..D[len]中,找到最大的j,满足D[j] < A[t]。令k = j + 1,则有D[j] < A[t] <= D[k],将A[t]接在D[j]后将得到一个更长的上升子序列,同时更新D[k] = A[t]。最后,len即为所要求的最长上升子序列的长度。

在上述算法中,若使用朴素的顺序查找在D[1]..D[len]查找,由于共有O(n)个元素需要计算,每次计算时的复杂度是O(n),则整个算法的时间复杂度为O(n^2),与原来的算法相比没有任何进步。但是由于D[]的特点(2),我们在D[]中查找时,可以使用二分查找高效地完成,则整个算法的时间复杂度下降为O(nlogn),有了非常显著的提高。需要注意的是,D[]在算法结束后记录的并不是一个符合题意的最长上升子序列!

这个算法还可以扩展到整个最长子序列系列问题,整个算法的难点在于二分查找的设计,需要非常小心注意。

 

介绍二:

最长上升子序列LIS算法实现  最长上升子序列问题是各类信息学竞赛中的常见题型,也常常用来做介绍动态规划算法的引例,笔者接下来将会对POJ上出现过的这类题目做一个总结,并介绍解决LIS问题的两个常用算法(n^2)和(nlogn).

问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7....an,求它的一个子序列(设为s1,s2,...sn),使得这个子序列满足这样的性质,s1<s2<s3<...<sn并且这个子序列的长度最长。输出这个最长的长度。(为了简化该类问题,我们将诸如最长下降子序列及最长不上升子序列等问题都看成同一个问题,其实仔细思考就会发现,这其实只是<符号定义上的问题,并不影响问题的实质)

例如有一个序列:1 7 35 9 4 8,它的最长上升子序列就是 13 4 8 长度为4.

算法1(n^2):我们依次遍历整个序列,每一次求出从第一个数到当前这个数的最长上升子序列,直至遍历到最后一个数字为止,然后再取dp数组里最大的那个即为整个序列的最长上升子序列。我们用dp[i]来存放序列1-i的最长上升子序列的长度,那么dp[i]=max(dp[j])+1,(j∈[1, i-1]); 显然dp[1]=1,我们从i=2开始遍历后面的元素即可。

算法2(nlogn):维护一个一维数组c,并且这个数组是动态扩展的,初始大小为1,c[i]表示最长上升子序列长度是i的所有子串中末尾最小的那个数,根据这个数字,我们可以比较知道,只要当前考察的这个数比c[i]大,那么当前这个数一定能通过c[i]构成一个长度为i+1的上升子序列。当然我们希望在C数组中找一个尽量靠后的数字,这样我们得到的上升子串的长度最长,查找的时候使用二分搜索,这样时间复杂度便下降了。

石子合并(NOI’95

一、问题描述

在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分.            


输入数据:

文件名由键盘输入,该文件内容为:

       第一行为石子堆数N;

       第二行为每堆石子数,每两个数之间用一空格分隔.

 

输出数据 :

 输出文件名为OUTPUT.TXT

      从第1至第N行为得分最小的合并方案. 第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.

      每种合并方案用N行表示,其中第i行(1≤i≤N)表示第i次合并前各堆的石子数(依顺时钟次序输出,哪 一堆先输出均可). 要求将待合并的两堆石子数以相应的负数表示,以便识别,参见MODEL2.TXT

参考输入文件EXAMPLE2.TXT        

4

4 5 9 4

 

参考输出文件MODEL2.TXT

-4 5 9 -4

-8 -5 9

-9 -13

-22

 

4 -5 -9 4

4 -14 -4

-4 –18

-22

二、分析

看到本题,容易想到使用贪心法,即每次选取相邻最大或最小的两堆石子合并。

然而这样做对不对呢?看一个例子。

N=5   石子数分别为3 4 6 5 4 2。

用贪心法的合并过程如下:

第一次 3 4 65 4 2得分 5

第二次 5 4 65 4得分9

第三次 9 6 5 4得分9

第四次 9 6 9得分15

第五次 15 9得分24

第六次24

总分:62

然而仔细琢磨后,发现更好的方案:

第一次3 4 65 4 2得分 7

第二次7 6 54 2得分13

第三次13 5 4 2得分6

第四次13 5 6得分11

第五次 13 11得分24

第六次24

总分:61

显然,贪心法是错误的。

为什么?

显然,贪心只能导致局部的最优,而局部最优并不导致全局最优。

仔细分析后,我们发现此题可用动态规划进行解决。

我们用data[I,j]表示将从第i颗石子开始的接下来j颗石子合并所得的分值,

max[i,j]表示将从第i颗石子开始的接下来j颗石子合并可能的最大值,那么:

max[I,j] = max(max[i, k] + max[i + k, j – k] + data[I,k] + data[I + k, j – k]) (2<=k<=j)

max[i,1] = 0

同样的,我们用min[i,j]表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值,可以得到类似的方程:

min[I,j] = min(min[i, k] + min[i + k, j – k] + data[I,k] + data[I + k, j – k]) (0<=k<=j)

min[I,0] = 0

这样,我们完美地解决了这道题。空间复杂度为O(n2),时间复杂度也是O(n2)。

动态规划思路:
   阶段i:石子的每一次合并过程,先两两合并,再三三合并,...最后N堆合并
   状态s:每一阶段中各个不同合并方法的石子合并总得分。
   决策:把当前阶段的合并方法细分成前一阶段已计算出的方法,选择其中的最优方案
   具体来说我们应该定义一个数组s[i,j]用来表示合并方法,i表示从编号为i的石头开始合并,j表示从i开始数j堆进行合并,s[i,j]为合并的最优得分。
   对于上面的例子来说,初始阶段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1],因为一开始还没有合并,所以这些值应该全部为0。
   第二阶段:两两合并过程如下,其中sum(i,j)表示从i开始数j个数的和
              s[1,2]=s[1,1]+s[2,1]+sum(1,2)
              s[2,2]=s[2,1]+s[3,1]+sum(2,2)
              s[3,2]=s[3,1]+s[4,1]+sum(3,2)
              s[4,2]=s[4,1]+s[5,1]+sum(4,2)
              s[5,2]=s[5,1]+s[6,1]+sum(5,2)
              s[6,2]=s[6,1]+s[1,1]+sum(6,2)
第三阶段:三三合并可以拆成两两合并,拆分方法有两种,前两个为一组或后两个为一组
         s[1,3]=s[1,2]+s[3,1]+sum(1,3)或s[1,3]=s[1,1]+s[2,2]+sum(1,3),取其最优
         s[2,3]=s[2,2]+s[4,1]+sum(2,3)或s[1,3]=s[2,1]+s[3,2]+sum(2,3),取其最优
                             ...

第四阶段:四四合并的拆分方法用三种,同理求出三种分法的得分,取其最优即可。以后第五阶段、第六阶段依次类推,最后在第六阶段中找出最优答案即可

凸多边形三角划分(HNOI’97

一、试题描述

给定一个具有N(N<50)个顶点(从1到N编号)的凸多边形,每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形,使得这些三角形顶点的权的乘积之和最小?

输入文件:第一行 顶点数N

          第二行 N个顶点(从1到N)的权值

输出格式:最小的和的值

          各三角形组成的方式

输入示例:5

121  122  123  245 231

输出示例:The minimum  is :12214884

          The  formation of 3 triangle:

          3 4 5, 15 3, 1 2 3

二、试题分析

这是一道很典型的动态规划问题。设F[I,J](I<J)表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积,我们可以得到下面的动态转移方程:

F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}     (I<K<J)

目标状态为:F[1,N]

但我们可以发现,由于这里为乘积之和,在输入数据较大时有可能超过长整形甚至实形的范围,所以我们还需用高精度计算,但这是大家的基本功,程序中就没有写了,请读者自行完成。

乘积最大(noip’2000)

问题描述:

一道题目:设有一个长度N的数字串,要求选手使用K个乘号将它分成K+1个部分,找出一种分法,使得这K+1个部分的乘积能够为最大。同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子:

有一个数字串: 312,当N=3,K=1时会有以下两种分法:

1)3*12=36

2)31*2=62

这时,符合题目要求的结果是: 31*2=62

输入:程序的输入共有两行:

第一行共有2个自然数N,K(6<=n<=40,1<=k<=6)

第二行是一个K度为N的数字串。

输出:结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数)。

输入

4 2

1231

输出

62

分析:

设字符串长度为n,乘号数为k,如果n=50,k=1时,有(n-1)=49种不同的乘法,当k=2时,有C(2,50-1)=1176种乘法,既C(k,n-1)种乘法,当n、k稍微大一些的时候,用穷举的方法就不行了。

   设数字字符串为a1a2…an

   K=1 时:一个乘号可以插在a1a2…an中的n-1个位置,这样就得到n-1个子串的乘积:

      a1*a2…an, a1a2*a3…an, …, a1a2…a n-1*an( 这相当于是穷举的方法)

   此时的最大值= max{a1*a2…an,a1a2*a3…an, …, a1a2…a n-1*an }

      K=2时,二个乘号可以插在a1a2…an中n-1个位置的任两个地方, 把这些乘积分个类,便于观察规律:

   ①最后一个数作为被乘数:

  a1a2 …*a n-1*an , a1a2 …*a n-2 a n-1*an , a1*a2 …a n-3 a n-2 a n-1*an

  设符号F[n-1,1]为在前n-1个数中插入一个乘号的最大值,则的最大值为F[n-1,1]*an

   ②最后2个数作为被乘数:

  a1a2 …*a n-2*a n-1an , a1a2 …*a n-3 a n-2* an-1 an , a1*a2 …an-3 a n-2*an-1an

设符号F[n-2,1]为在前n-2个数中插入一个乘号的最大值,则的最大值为F[n-2,1]*an-1an

   ③最后3个数作为被乘数:

设符号F[n-3,1]为在前n-3个数中插入一个乘号的最大值,则最大值为F[n-3,1]+an-2an-an

   ……

  a3~an作为被乘数:F[2,1]*a3 …an-2an-1an

  此时的最大乘积为:

F[n,k]=max{F[n-1]*an,F[n-2,1]*an-1an,F[n-3,1]*an-2an-1an,F[2,1]*a3…an-2an-1an}

  设F[i,j]表示在 i 个数中插入 j 个乘号的最大值,g[i,j]表示从ai到aj的数字列,则可得到动规方程:

F[I,j]= max{F[I-1,j-1]*g[I,I],F[I-2,j-1]*g[I-1,I],F[I-3,j-1]*g[I-2,I],

…,F[j,j-1]*g[j+1,I]}(1<=I<=n, 1<=j<=k)

  边界: F[I,0] =g[1,I] (数列本身)

  阶段:子问题是在子串中插入j-1,j-2……1,0个乘号,因此乘号个数作为阶段的划分(j个阶段)

  状态:每个阶段随着被乘数数列的变化划分状态。

  决策:在每个阶段的每种状态中做出决策。

  还有2个问题需要注意:

 (1)输入的字符需要进行数值转换

 (2)由于乘积可能很大,所以可以使用大数类型

参考程序

 

系统可靠性(HNOI’98

一、问题描述:

给定一些系统备用件的单价Ck,以及当用Mk个此备用件时部件的正常工作概率Pk(Mk),总费用上限C。求系统可能的最高可靠性。

输入:第一行:n  C

第二行:C1  P1(0)  P1(1) … P1(X1) (0<=X1<=[C/Ck])

         …

第 n 行:Cn  Pn(0) Pn(1) … Pn(Xn) (0<=Xn<=[C/Cn])

输出:最大可靠性的值

样例

输入:

2  20                                                         

3  0.6 0.65  0.7  0.75 0.8  0.85  0.9

5  0.7 0.75  0.8  0.8 0.9

输出:0.6375

二、算法分析

    1.证明这个问题符合最优化原理。可以用反证法证明之。假设用money的资金购买了前I项备用件,得到了最高的系统可靠性,而且又存在如下情况:对于备用件I,设要买Ki个,则可用的资金还剩余money– Ci*Ki,用这些钱购买前(I-1)项备用件,如果存在一种前(I-1)种备用件的购买方案得到的系统可靠性比当前得到的要高,那么这个新的方案会使得整个前I项备用件组成的系统可靠性比原先的更高,与原假设矛盾。所以可以证明这个问题符合最优化原理。

2.证明这个问题符合无后效性原则。

3.综上所述,本题适合于用动态规划求解。

4.递推方程及边界条件:

   F[I,money] :=max { F[I-1,money – C[I]*K[I] ] } (0<=K[I]<=C div Ci )

三、参考程序

过河(noip’2005)

一、             问题描述

在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。

  题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

  对于30%的数据,L <= 10000;

  对于全部的数据,L <= 10^9。

输入:第一行有一个正整数L(1 <= L <= 10^9),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开

输出:输出只包括一个整数,表示青蛙过河最少需要踩到的石子数。

样例:10

2 3 5

2 3 56 7 

输出:2

分析:

1.分s=t和s<t考虑。当s=t时,只需要考虑第i个位置上有石子且i mod s=0的情况;
2.当s<t时,压缩桥长和石子位置(要考虑到石子位置不一定有序),若两石子间空白区>maxk+2*t,我们就把它缩短为前一个石子位置加上maxk+2*t(可证得maxk=100时满足所有区间);
3.从1到L(压缩后最后一个石子位置)+t-1进行动态规划,f[i]=min{f[i-j]+1(如果i处不为石子),f[i-j](如果i处为石子)}(j=s..t,f[i]初始值为100,最多有100颗石子);
4.答案就是min{f[L],f[L+1],...,f[L+t-1]}。

这题因为 1 <= L <= 10^9 L非常大,只能进行状态压缩。如果 L小到可以开数组,我们可以设一个数组Dp[L_MAX]保存每个子状态,从后往前DP,Dp[n] 表示从坐标位置 n 跳到或者跳过终点的最优解(局部最优),求Dp[n-1],Dp[n-1] = min{Dp(n-1+minJump ~ n-1+maxJump)},minJump表示青蛙最小的跳数,maxJump表示青蛙最大的跳数,如果 n-1 位置有石头则Dp[n-1]=Dp[n-1]+1.

比如对于示例:

10

2 3 5

2 3 56 7

首先我们初始化数组,Dp[]={0},从坐标位置7开始算,Dp[7]=min{Dp(2+7,3+7)}=0,因为7位置有石头所以Dp[7]=Dp[7]+1=1,同理,Dp[6]=1,Dp[5]=1,Dp[4] = min{Dp(4+2,4+3)} = 1,因为5位置没有石头所以Dp[4]不用加1,最后可求得 Dp[] = {2,1,2,2,1,1,1,1,0,0,0 ……},Dp[0]即为全局的最优解,表示从起点跳到或者跳过终点青蛙最少要踩到的石头数目。

 

这题因为L很大,子状态不能全部保存,我们观察到,当求Dp[n]的值时用到的状态只有

Dp(n+minJump,n+maxJump)所以我们可以不用全部保存每个坐标位置的Dp值,而只要保存从n位置之后最多maxJump个坐标的Dp值即可。为此我们可设Dp[maxJump](对本题可设Dp[10]),注意这里的下标不表示坐标位置,我们可用一个变量nHeadStart跟踪坐标位置,当求n位置的Dp值时,nHeadStart=n+1。到这里我们解决了空间问题,真正难理解的是下面的状态压缩。

 

假如测试数据是:

1000000000

2 5 5

2 6 510 99999999

 

99999999这个位置的Dp值我们知道是 1,而该位置前面有99999999-10个位置都没有石头,我们不可能也没有时间去求所有这些中间位置的Dp值,但是10位置的值却与这中间的有关,HowCan I do ???假如有这样一组Dp值,Dp[]={25 1 3} 我们观察到单minJump != maxJump时,因为每次都取最小值所以经过有限步运算后,Dp={1 1 1 1},即所有的Dp值都变成开始计算时的最小值。变化经过如下

数据:minJump=2, maxJump=3,Dp[]={2,5,1,3}

Dp[]={1,2,5,1}

Dp[]={1,2,2,5}

Dp[]={2,1,2,2}

Dp[]={1,2,1,2}

Dp[]={1,1,2,1}

Dp[]={1,1,1,2}

Dp[]={1,1,1,1}

即从当前位置到前面 7 个及 7 个以前的空位(没有石头),我们断定Dp[]={1,1,1,1}

因此,对 2 6 5 10 99999999,我们可以知道从 11 位置开始,Dp[]={0,0,0,0,0}(只需保存maxJump个)前面的就好做了。经过几步的空位可以达到稳定状态(我称Dp数组值不再变化的状态为稳定态),我们有两种方法

其一:每求一个空位后我们求Dp数组中的最值,如果最大和最小值相等就达到稳定态了。这种方      法因为每次都要求最值,因此当maxJump比较大的时候不适合。

其二:我们可以断定如果当前位置之前至少有maxJump*maxJump个空位,就一定会出现稳定态(请读者自己理解 这样我们遇到空位大于等于maxJump*maxJump时直接设Dp数组为最小值。

 

上面的是minJump != maxJump的情况,当minJump==maxJump时,假如Dp[]={0,0,1}

数据:minJump=3, maxJump=3,Dp[]={0,0,1},Dp的变化情况如下:

Dp[]={1,0,0}

Dp[]={0,1,0}

Dp[]={0,0,1}

   ......

出现重复的情况,且min{Dp[]} != max{Dp[]},因此不能按minJump !=maxJump的情况处理。这种情况只要将重复出现的位去掉即可,比如上面的如果当前位置前有  4 个空位,前三个不用计算,因为到第三个位置的Dp值和当前的Dp值一样。

 

Dp[]数组的下标变化大家可以参考循环队列的情况。

关于压缩空长条步数的证明

 

对于步幅s到t 若目标位置距起始点距离D≥s×(s+1)则一定可以到达目标点

证明:

设一次可以走p步或p+1 方便起见,我们取起始位置为坐标0点

那么p×(p-1)点一定可以达到(每次走p的距离,走p-1次)

因为我们也可以每次走p+1步

所以可以通过将一次p距离的行走替换为p+1距离的行走来实现总距离+1

比如说我们要达到p×(p-1)+1点我们只需要走p-2次p的距离和一次p+1的距离即可到达

我们整理两个表达式p×(p-1)+1和(p-2)×p+(p+1)就可证明上述正确

现在我们从(p

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/luyuncheng/article/details/8952072

智能推荐

匿名内部类用法总结-程序员宅基地

文章浏览阅读330次。java中的匿名内部类总结 匿名内部类也就是没有名字的内部类 正因为没有名字,所以匿名内部类只能使用一次,它通常用来简化代码编写 但使用匿名内部类还有个前提条件:必须继承一个父类或实现一个接口 实例1:不使用匿名内部类来实现抽象方法 abstract class Perso..._匿名内部类用法代码

tiny6410用usb-wifi命令行连wifi问题-程序员宅基地

文章浏览阅读183次。最近要将tiny6410连上网,自己做的文件系统没有移植qtopia,所以用命令行上网,直接拷了友善的scan-wifi和start-wifi。stop-wifi来用, 刚开始scan-wifi可以搜到所有无线网络。 [root@FriendlyARM /]# scan-wifi cf..._scan-wifi

matlab cgf sc 未定义,CVPR09-ScSPM - 源码下载|数值算法/人工智能|matlab例程|源代码 - 源码中国...-程序员宅基地

文章浏览阅读102次。CVPR09-ScSPM\ScSPM\dictionary\dict_Caltech101_1024.mat............\.....\large_scale_svm\lbfgs2.m............\.....\...............\li2nsvm_grad.m............\.....\...............\li2nsvm_lbfgs.m......._cvpr09-scspm

LINUX下安装oracle的java字体问题-程序员宅基地

文章浏览阅读124次。2. Java , Installanywhere 在 Redhat 上的中文问题解决方法 jacklondon [原作] 标准 jre/jdk 中只带了 redhat 6 的 font.properties, 我在 r..._linux 环境java oracle jdk读取不到字体

rocketMQ避坑记录(附docker环境下设置brokerIP1解决方案)-程序员宅基地

文章浏览阅读4.9k次。环境配置1、 推荐使用64位OS,Linux/Unix/Mac2、 64bit JDK 1.8+3、 Maven 3.2.x 注意:在搭建rocketMQ前,需配置好JDK1.8,若用source release版需配置maven环境rocketMQ下载地址source re..._rocketmq docker修改ip

Maven类包冲突解决终极小技巧-程序员宅基地

文章浏览阅读61次。Maven对于新手来说是《步步惊心》,因为它包罗万象,博大精深,因为当你初来乍到时,你就像一个进入森林的陌生访客一样迷茫。Maven对于老手来说是《真爱配方》,因为它无所不能,利如刀锋,使用Maven做开发,如饮美酒如悦美人。Maven对于新手来说,最痛苦的一件事莫过于包之间的冲突,由...

随便推点

Vue和React的异同点,及技术选型_vue和react谈谈区别和选型考虑-程序员宅基地

文章浏览阅读813次。Vue和React的异同点,及技术选型_vue和react谈谈区别和选型考虑

掌握g2o边的代码套路--从零开始一起学习SLAM-程序员宅基地

文章浏览阅读281次。  小白:师兄,g2o框架《从零开始一起学习SLAM | 理解图优化,一步步带你看懂g2o代码》,以及顶点《从零开始一起学习SLAM | 掌握g2o顶点编程套路》我都学完啦,今天给我讲讲g2o中的边吧!是不是也有什么套路?   师兄:嗯,g2o的边比顶点稍微复杂一些,不过前面你也了解了许多g..._g2o中setparameterid

只用html+css做出会跳动爱心_html+css构建动态爱心-程序员宅基地

文章浏览阅读6.3k次,点赞11次,收藏50次。【代码】只用html+css做出会跳动爱心。_html+css构建动态爱心

如何实现SIP协议与WebRTC协议与互通-2_移动端 sip webrtc sdk-程序员宅基地

文章浏览阅读2.1w次。如何实现SIP协议与WebRTC协议与互通-2不需要付费使用sdk,通过sip协议代理。即可快速实现sip与webrtc协议互通和webrtc与sip协议互通可私有化临近节点部署,最高支持上万并发!SIP协议与RTC协议是分属两个音频编解码协议,WebRTC使用JSEP协议建立会话,SIP协议是IMS网络广泛使用的信令协议,要实现webRTC协议和SIP协议互通,要从信令层和媒体层进行处理。以下为WebRTC和SIP协议互通的技术架构图。有需要可以讨论具体技术方案!..._移动端 sip webrtc sdk

xz压缩文件方法或命令_了xz.z-程序员宅基地

文章浏览阅读1.3k次。xz压缩文件方法或命令xz -z 要压缩的文件 如果要保留被压缩的文件加上参数 -k ,如果要设置压缩率加入参数 -0 到 -9调节压缩率。如果不设置,默认压缩等级是6.xz解压文件方法或命令xz -d 要解压的文件 同样使用 -k 参数来保留被解压缩的文件。 创建或解压tar.xz文件的方法习惯了 tar czvf 或 tar xzvf 的人可能碰到 _了xz.z

HFSS相关操作简述_hfss平面变为立体-程序员宅基地

文章浏览阅读1.3w次,点赞5次,收藏23次。HFSS中的面怎么拉伸为体?(如何把一个不规则的平面图形变成厚度一定的立体图形?)先使用线段绘制出一个封闭平面图形,然后选中右击,Edit–>Sweep–>Along Vector;向哪个方向拉伸,就将视图修改为什么方向。如想向Z方向拉伸,则将视图修改为YZ或XZ,选中一个点进行拉伸即可。HFSS中曲线连接如何连接为面各段曲线要先布尔相加,弄成闭合曲线;再选中由分段曲线组成的闭合曲线,右键,Edit–>Surface–>Cover Lines。HFSS怎么导入DXF或D._hfss平面变为立体