网上找的一些动态

1、动态规划题(扩充中)tju1004 防御题目：Problem某国为了防御敌国的，发展出一种系统。但是这种系统有一个缺陷：虽然它的第一发 弹能够达到任意的高度，但是以后每一发 弹都不能高于前一发的高度。某天，捕捉到敌国的来袭。由于该系统还在使用阶段，所以只有一套系统，因此有可能不能所有的。Input最多 20 个整数，分别表示依次飞来的高度（给出高度数据是不大于 30000的正整数）Output两个整数M 和N。表示：这套系统最多能M套这种枚，如果要所有最少要配备 N系统。Sle Input300 250 275 252 200 138 245S5 2le Output算法：这道题就是典型的最长

2、单调序列和最长单调序列的覆盖问题，两个问题分别求。问题一：求最长单调序列的长度。设opti表示从 A1 到 Ai 的最长单调序列长度，则：opt1=1opti=maxoptk+1 (1=k=Ai)最后输出 optn.问题二：最长单调序列的覆盖个数可以不断求出最长单调序列，把它们从序列集合中删去，直到集合为空集，在此过程中进行累加。复杂度：方法的时间复杂度为o(n2)，tju1004 已经可以 Accepted，但是如果 n1000000 时，速度显然不如人意。改进：有没有更好的方法呢？当然有！最长单调序列，顾名思义，单调的，即：Ak= )Ai (ki)于是难道不可以只保存最后一个数？首先,开一

3、个足够大的数组?A:array1.maxnof longAi表示长度为 i 的最长单调序列的最后一个数字，程序如下：procedure main; var .beginfillchar(a,sizeof(a),0); ans:=0; 最长单调序列的长 readln(n);for s:=1 to n do begin read(x);l:=1; r:=ans; 左、右范围 whl=r do begin 二分m:=(l+r) shr 1;if amans then inc(ans); 新建，即长度为 ans+1 的最长单调序列出现了！ al:=x;end;end;最长单调序列的覆盖个数也很好求，只

4、要将if am=x then l:=m+1 elser:=m-1 中的=即可，其它类似。算法的复杂度显然降低了！疑问：为什么只要将 if am=x then l:=m+1 else r:=m-1 中的=即可？tju1039 核电站问题题目：Problem一个核电站有N 个放核物质的坑，坑排列在一条直线上。如果连续M 个坑中放入核物质，则会发生，于是，在某些坑中可能不放核物质。任务：对于给定的N 和M，求不发生的放置核物质的方案总数Input该题有多组测试数据，每组数据一行，两个正整数N，M( 1N50，2M5)Output每组数据只输出一个正整数S，表示方案总数。S4 3le InputSle

5、 Output13算法:这道题似乎可以用容斥定理来做，但要实现几乎不可能，运算中的数据会很大，即使高精度也很慢很烦。很自然的想到了可以用动态规划算法。开始试探两个元素的 dp，设:fi,j表示前 i 个坑放置j 个核物质时的放置总方案数，那么似乎fi,j= fi-1,j-1当 j0在第i 个坑放核物质不在第i 个坑放核物质fi-1,j当j=0但程序编好后,发现结果不对，因为有情况没考虑到?如果在第 i 个坑放核物质，那么也许前i-1 个坑里j-1 个核物质放在最后连续j-1 个坑里，在这种情况下在第i 个坑放核物质是不允许的！只好再增加一个参数k,fi,j,k表示前 i 个坑放置j 个核物质且

6、最后连续放置k 个核物质时的放置总方案数，那么fi,j,k= fi-1,j-1,k-1当k0 fi-1,j,l 当 k=0最后用个二重循环统计一下，大功告成！复杂度：很显然时间复杂度为o(n3)，空间复杂度为 o(n3)，使用滚动数组可降一维。疑问：虽然 dp 可以通过，但很可能有更好的算法（如公式），目前没有找到，但有一发现：Ans(n,m)= 2n-omega当n-m 不变，omega 为常数，问题是omega 与n-m 到底关系？tju1048 Tom 的烦恼题目：ProblemTom 是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用有限的开了一家汽车零件，专门为汽车

7、制造商制造零件。由于有限，他只能先一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他加工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是的，但开始和结束时间相同不算）。Tom 当然希望能把所有的零件都加工完，以得到的加工费，但当一些零件的加工时间要求有时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得尽量多的加工费，Tom 不知如何进行取舍。现在请你帮Tom 设计一个程序，合理选择部分（或全部）零件进行加工，使得得到最大的加工费。Input第一行是一个整数 m,表示测试数据的个数。每组测试数据的

8、第一行是一个整数n(n=30000)，表示共有 n 个零件须加工。接下来的n 行中，每行有 3 个整数，分别表示每个零件加工的时间要求。第一个表示开始时间，第二个表示该零件加工的结束时间，第三个表示加工该零件可以得到的加工费。注：数据中的每个数值不会超过 100000.Output对每组测试数据,输出一个整数，表示 Tom 可以得到的最大加工费。Sle Input525Sle Output30算法：这一题要用动态规划解决。设：fi表示到达时间 i 时所能得到的最大加工费，则：fi= maxfk-1+vk,i (0ki) 其中，(k,i)是输入数据中给的一段时间,vk,i表示这段时间内的加工费。

9、最后输出 f30000即可。改进：首先，将结束时间作为关键字排序，至于数组 ai中，以便处理。随后，在查找是否存在时间(k,i)时只需用一个指针来控制即可。复杂度：时间复杂度为 o(n2)，空间复杂度为 o(n)，全部数据能在 1s 内通过！疑问：有没有更好的算法呢？tju1049 砝码问题题目：Problem有一组砝码，重量互不相等，分别为 m1、m2、m3mn；它们可取的最大数量分别为 x1、x2、x3xn。现要用这些砝码去称物体的重量,问能称出多少种不同的重量。Input第一行为一整数 t,表示有 t 组测试数据。每组测试数据第一行一个整数n（n=10），表示有多种不同的砝码；第二行n

10、个整数（中间用空格分隔），m1、m2、m3mn，分别表示 n 个砝码的重量；（1=mi=20）第三行n 个整数（中间用空格分隔），x1、x2、x3xn，分别表示 n 个砝码可取的最大数量。（1=xi=20）Output每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数。注：包括 0。S 121 22 1le InputS5le Output算法：看到这道题很容易联想到典型的背包问题，只是有一点变化。设：型的 fi,j表示前 i 个砝码能否称出重量j，则：f0,0:=truefi,j:=fi,j or fi-1,j-k*mi (1=k=0)最后用个一重循环统计一下 fn,p(

11、0=p=maxm)有多少个值为 true 的即可。改进：空间不够时可以用滚动数组来降一维，其实不只如此。不仅要注意到第i 个状态只与第i-1 个状态有关，还可以发现j-k*mij!所以连滚动数组都不需要，只需直接用一个数组从头到尾一下！复杂度：经过优化，时间复杂度为o(n2)，空间复杂度为 o(n)，应该比较理想。tju1050 单词的划分题目：Problem有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。出于减少分析量的目的，希望划分出的单词数越少越好。你就是来完成这一划分工作的。Input第一行为一整数T，表示有T 组测试数据

12、。每组测试数据第一行为一字符串。(长度小于 256)第二行为一整数N。（1=N=100）以下N 行，每行一个单词。Output一个整数，表示字符串可以被划分成的最少的单词数。S1le Inputrealityour 5real reality it yourourS2le Output算法：这道题比较容易能想到用dijkstra 来求最短路径，有另一种的方法?动态规划。（其实，这里的动态规划也可以理解为在求最短路径）首先，用类似邻接矩阵的型的li,j表示从 i 到j 是不是单词。设：fi表示前i 个串能分成的最少单词数，很简单地得到：f0= 0fi= minfk+1 (0=ki)&(从 k+1

13、 到j 是单词)（默认从 0 到 0 是单词）改进：可以像tju1048 Tom 的烦恼那样，先排一下序再 dp。想必不用具体阐述了。复杂度：经过优化的时间复杂度为o(n2)，可以 Accepted。tju1059 数的计数题目：Problem先输入一个自然数n(n3000000)，然后对此自然数按照如下方法进行处理1?不作任何处理:2?在它的左边加上一个自然数，但该自然数过原数的一半;3?加上数后，继续按此规则进行处理，直到不能再而 自然数为止。例如 n=66162612636136所以满足要求的个数为 6。Input包含多个测试数据,每行是一个整数 n(1=n=3000000)Output

14、一个整数,表示解的个数(保证不超过 50 位)S6le InputS6le Output算法：这道题在许多书上都有介绍，设：fi表示 i 个数的f1= 1，则：fi= fk改进 1：算法虽然经典，但时间复杂度为 o(n2)，如此大的数据显然要超时，能不能降低一维呢？换一种构造就行了！假如g1 =1设gi表示 f1到 fi总和，那么gi =gi-1+gi|2时间复杂度降到了 1 维！ans1= 1ansi= gi-gi-1改进 2：不难看出，在解出 gi后，gk(1=ki)都出来了，那么可以在程序的开头做一下预处理，这是极大的优化！改进 3：尽管时间降低到一维，但数据很大(保证不超过 50 位)

15、!于是不得不用高精度运算，但如果这样，时间复杂度不就又二维了吗？可以用压缩数组来避免。即：每一位数的范围由 0 到 9 扩大到 0 到 9999999，这样 50位数最多只用 8 位，o(8n)与 o(n)相差不大。改进 4：尽管做了 3 次改进，但空间上还是需要优化(1=n=3000000，开不到！)。发现 ansi=gi-gi-1，将这个式子拆开，便是：ansi =gi-gi-1 =gi-1+gi|2-gi-1 =gi|2而(1=n=3000000)，所以在做预处理时只要把 1500000 以内的只求出就行了！而空间上也只需开一个 1.1500000 的数组。经过以上四步改进，最终 AC

16、了！复杂度：时间复杂度o(n)，空间复杂度 o(n)。疑问：本人将 f1= 1fi= fk进行重新构造后得出了，如果用组合数学的方法解此递推式，是否能更好呢？本人尚不清楚，但本题方法值得一珍藏！tju1063 硬币题目:Problem知道即使是同一种面值的硬币，它们的重量也有可能不一样，因为它受到许多的影响，包括制造工艺和流程上的。但是任何一种面值的硬币的重量总是处于某个特定范围之内。现在已知所有面值的硬币的重量范围。给定一堆硬币的总重量，问这堆硬币的总价值有多少种不同的可能。举例：已知一角硬币的重量在 19 到 21 之间，五角硬币的重量在 40 到 43 之间。有一堆硬币的总重量为 99。

17、则它可以由 4 个重量为 20，1 个重量为 19 的一角硬币组成，其总价值为 5 角，也可以由 1 个重量为 42 的五角硬币和 3 个重量为 19 的一角硬币组成，其总价值为 8 角，再或者由 2 个重量为 40的五角硬币和 1 个重量为 19 的一角硬币组成，其总价值为 1 块 1 角。因此这堆硬币的总价值共有 3 种不同的可能。Input该题含有多组测试数据。每组测试数据第一行是一个整数w（10=w=100）表示所有硬币的总重量。第二行是一个整数n（1=n=7）表示不同面值的硬币总数。接下来n 行每行 3 个整数，依次表示硬币的面值，最小可能重量和最大可能重量。硬币面值不超过 50，最

18、小重量不低于 2，最大重量不高于 100。最大重量和最小重量之间的差距不超过 30。Output每组数据输出仅包括一行表示这堆硬币的总价值有多少种不同的可能性。Sle Input9921 19 215 40 43S3le Output算法：此题的动态规划也不难，构造是关键，的可能，那么：f0,0,0= true设：型的 fk,i,j表示前 k 项是否有总值为i 而总重为jfk,i,j= fk,i,j or fk-1,i-value,j-weight下面就不用再具体说了。tju1077题目：Problem猫认为自己很强，于是找彩虹。彩虹接受了，两人都有一定的血HP1、HP2。HP1 是猫的，HP

19、2 是彩虹的。他们也有一定力 AP1、AP2，AP1 是猫的，AP2 是彩虹的。当进行HP21 AP11时，对方的 HP 减少自己的力，比如 HP12AP21，当彩虹猫时，猫的 HP2（HP1）1（AP2）1。现在两个人对决很多回合，每回合不是猫彩虹，就是彩虹猫。求猫能赢彩虹的胜率。保留 4 位小数。Input该题含有多组测试数据,每行为 HP1,HP2,AP1 和AP2 （1=HP1,HP2,AP1,AP2=32767）Output每组数据输出一行，为猫赢彩虹胜率的值Sle Input2 1 1 1Sle Output75.0000算法：这道题虽然动态规划不完备，但 tju 上过了。方程想必

20、人人会列，fi,j=0.5*(fi-1,j+fi,j-1)但动态规划在这题中并不是最好的，更提倡用组合数学里的公式！疑问：什么样的公式最好？tju1078 祝福题目：Problem得知antis 即将沉没的消息以后，King 决定把他的人民送到安全的国外去。但是码头已经废弃很多很多年了。码头前有一个迷宫，国王的骑士只身闯入了这个迷宫骑士在迷宫的出口遇到了不明生物的！骑士因为是单独，所以很快便招架不住了，他的大马被打得奄奄一息（。）这个时候，迷宫中的两座石像(一个是猫，一个是天使。（！)里放出了无数锋利的刀片，把不明生物全部杀死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上多了一个戒指，上面写着：“这个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每次移动如果是只要|x-x1|+|y-y1| (x1,y1)的移动！”(Angel 暗自想：还有这么心黑的)迷宫为n*m 的矩阵。骑士从(n,到(1,。问：在戒指的帮助下，骑士最少要多少步才能回到？在步数最少的前提下，总共有多少种办法到达？注意，骑士不会傻到一直停留在原地不动。Input该题含有多组测试数据,对于每组数据, 第 1 行 3 个整数，n, m,(1=n,m=20)和 P(P=50)，分别代