2006/10/17
conclusion of dp problems
KISSYOU
态规划题目总结 by pcpcpc
这是我曾经做过的总结，很值得珍藏！！！
同济大学编程题库动态规划题目总结
作者：pcpcpc
tju1004 防御导弹
题目：
Problem
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系
统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹
都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在
使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
Input
最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000
的正整数）
Output
两个整数M和N。表示：这套系统最多能拦截 M
枚导弹，如果要拦截所有导弹最少要配备 N 套这种导弹系统。
Sample Input
300 250 275 252 200 138 245
Sample Output
5 2
算法：
这道题就是典型的最长单调序列和最长单调序列的覆盖问题，两个问题分别求。
问题一：求最长单调序列的长度。
我们设opt[i]表示从A1到Ai的最长单调序列长度，则：
opt[1]=1
opt[i]=max{opt[k]+1} (1<=k=Ai)
最后输出opt[n].
问题二：最长单调序列的覆盖个数
我们可以不断求出最长单调序列，把它们从序列集合中删去，直到集合为空集，
在此过程中进行累加。
复杂度：
方法的时间复杂度为o(n^2)，tju1004已经可以Accepted，但是如果n>1000000时
，速度显然不如人意。
改进：
有没有更好的方法呢？当然有！
最长单调序列，顾名思义，单调的，即：A[k]<=(or >= > <)A[i] (k
首先,开一个足够大的数组??A:array[1..maxn]of longint
A[i]表示长度为i的最长单调序列的最后一个数字，程序如下：
procedure main;
var .............
begin
fillchar(a,sizeof(a),0);
ans:=0; {最长单调序列的长}
readln(n);
for s:=1 to n do begin
read(x);
l:=1; r:=ans; {左、右范围}
whlie l<=r do begin {二分}
m:=(l+r) shr 1;
if a[m]<=x then l:=m+1 else r:=m-1;
end;
if l>ans then inc(ans); {新建，即长度为ans+1的最长单调序列出现了！}
a[l]:=x;
end;
end;
最长单调序列的覆盖个数也很好求，只要将if a[m]>=x then l:=m+1 else
r:=m-1中的<=转换为>=即可，其它类似。算法的复杂度显然降低了！
疑问：
为什么只要将if a[m]>=x then l:=m+1 else r:=m-1中的<=转换为>=即可？
tju1039 核电站问题
题目：
Problem
一个核电站有N个放核物质的坑，坑排列在一条直线上。
如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质
。
任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数
Input
该题有多组测试数据，每组数据一行，两个正整数N，M( 1＜N＜50，2≤M≤5)
Output
每组数据只输出一个正整数S，表示方案总数。
Sample Input
4 3
Sample Output
13
算法:
这道题似乎可以用容斥定理来做，但要实现几乎不可能，运算中的数据会很大，
即使高精度也很慢很烦。我们很自然的想到了可以用动态规划算法。
我们开始试探两个元素的dp，设:f[i,j]表示前i个坑放置j个核物质爆炸时的放置
总方案数，那么似乎
f[i,j]= f[i-1,j-1] 当j>0 在第i个坑放核物质
f[i-1,j] 当j=0 不在第i个坑放核物质
但程序编好后,发现结果不对，因为有情况没考虑到??如果在第i个坑放核物质
，那么也许前i-1个坑里j-1个核物质放在最后连续j-1个坑里，在这种情况下在第
i个坑放核物质是不允许的！
我们只好再增加一个参数k,f[i,j,k]表示前i个坑放置j个核物质爆炸且最后连续
放置k个核物质时的放置总方案数，那么
f[i,j,k]= f[i-1,j-1,k-1] 当k>0
f[i-1,j,l] 当k=0
最后用个二重循环统计一下，大功告成！
复杂度：
很显然时间复杂度为o(n^3)，空间复杂度为o(n^3)，使用滚动数组可降一维。
疑问：
虽然dp可以通过，但很可能有更好的算法（如公式），目前没有找到，但有一发
现：
Ans(n,m)= 2^n-omega
当n-m不变，omega为常数，问题是omega与n-m到底有什么关系？？
tju1048 Tom的烦恼
题目：
Problem
Tom是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用
有限的资金开了一家汽车零件加工厂，专门为汽车制造商制造零件。由于资金有
限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他
加工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同
厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开
始和结束时间相同不算冲突）。
Tom当然希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件
的加工时间要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有
一台机器），为了赚得尽量多的加工费，Tom不知如何进行取舍。
现在请你帮Tom设计一个程序，合理选择部分（或全部）零件进行加工，使得
得到最大的加工费。
Input
第一行是一个整数m,表示测试数据的个数。
每组测试数据的第一行是一个整数n(n<=30000)，表示共有n个零件须加工。
接下来的n行中，每行有3个整数，分别表示每个零件加工的时间要求。
第一个表示开始时间，第二个表示该零件加工的结束时间，第三个表示加工该零
件可以得到的加工费。
注：数据中的每个数值不会超过100000.
Output
对每组测试数据,输出一个整数，表示Tom可以得到的最大加工费。
Sample Input
1
3
1 3 10
4 6 20
2 5 25
Sample Output
30
算法：
这一题要用动态规划解决。
设：f[i]表示到达时间i时所能得到的最大加工费，则：
f[i]= max{f[k-1]+v[k,i]} (0
[k,i]表示这段时间内的加工费。最后输出f[30000]即可。
改进：
首先，将结束时间作为关键字排序，至于纪录数组a[i]中，以便处理。
随后，在查找是否存在时间(k,i)时只需用一个指针来控制即可。
复杂度：
时间复杂度为o(n^2)，空间复杂度为o(n)，全部数据能在1s内通过！
疑问：
有没有更好的算法呢？
tju1049 砝码问题
题目：
Problem
有一组砝码，重量互不相等，分别为m1、m2、m3……mn；它们可取的最大数量分
别为x1、x2、x3……xn。
现要用这些砝码去称物体的重量,问能称出多少种不同的重量。
Input
第一行为一整数t,表示有t组测试数据。
每组测试数据第一行一个整数n（n<=10），表示有多种不同的砝码；
第二行n个整数（中间用空格分隔），m1、m2、m3……mn，分别表示n个砝码的重
量；（1<=mi<=20）
第三行n个整数（中间用空格分隔），x1、x2、x3……xn，分别表示n个砝码可取
的最大数量。（1<=xi<=20）
Output
每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数
。
注：包括0。
Sample Input
1
2
1 2
2 1
Sample Output
5
算法：
看到这道题很容易联想到典型的背包问题，只是有一点变化。
我们设：布尔型的f[i,j]表示前i个砝码能否称出重量j，则：
f[0,0]:=true
f[i,j]:=f[i,j] or f[i-1,j-k*mi] (1<=k<=xi)
(注意j-k*mi>=0)
最后用个一重循环统计一下f[n,p](0<=p<=maxm)有多少个值为true的即可。
改进：
空间不够时可以用滚动数组来降一维，其实不只如此。
我们不仅要注意到第i个状态只与第i-1个状态有关，还可以发现j-k*mi
复杂度：
经过优化，时间复杂度为o(n^2)，空间复杂度为o(n)，应该比较理想。
tju1050 单词的划分
题目：
Problem
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将
它划分成若干个部分，每个部分称为一个单词。
出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一
划分工作的。
Input
第一行为一整数T，表示有T组测试数据。
每组测试数据第一行为一字符串。(长度小于256)
第二行为一整数N。（1<=N<=100）
以下N行，每行一个单词。
Output
一个整数，表示字符串可以被划分成的最少的单词数。
Sample Input
1
realityour
5
real
reality
it
your
our
Sample Output
2
算法：
这道题比较容易能想到用dijkstra来求最短路径，有另一种的方法??动态规划
。（其实，这里的动态规划也可以理解为在求最短路径）
首先，用类似邻接矩阵的布尔型的l[i,j]表示从i到j是不是单词。设：f[i]表示
前i个串能分成的最少单词数，很简单地得到：
f[0]= 0
f[i]= min{f[k]+1} (0<=k
改进：
我们可以像tju1048 Tom的烦恼那样，先排一下序再dp。想必不用具体阐述了。
复杂度：
经过优化的时间复杂度为o(n^2)，可以Accepted。
tju1059 数的计数
题目：
Problem
先输入一个自然数n(n≤3000000)，然后对此自然数按照如下方法进行处理
1?不作任何处理:
2?在它的左边加上一个自然数，但该自然数不能超过原数的一半;
3?加上数后，继续按此规则进行处理，直到不能再而 自然数为止。
例如n=6
6
16
26
126
36
136
所以满足要求的个数为6。
Input
包含多个测试数据,每行是一个整数n(1<=n<=3000000)
Output
一个整数,表示解的个数(保证不超过50位)
Sample Input
6
Sample Output
6
算法：
这道题在许多书上都有介绍，我们设：
f[i]表示i个数的答案，则：
f[1]= 1
f[i]= f[k]
改进1：
算法虽然经典，但时间复杂度为o(n^2)，如此大的数据显然要超时，能不能降低
一维呢？
换一种构造就行了！
假如我们设g[i]表示f[1]到f[i]总和，那么
g[1] =1
g[i] =g[i-1]+g[i|2]
时间复杂度降到了1维！
ans[1]= 1
ans[i]= g[i]-g[i-1]
改进2：
我们不难看出，在解出g[i]后，g[k](1<=k
开头做一下预处理，这是极大的优化！
改进3：
尽管时间降低到一维，但数据很大(保证不超过50位)!
于是我们不得不用高精度运算，但如果这样，时间复杂度不就又重返二维了吗？
可以用压缩数组来避免。即：每一位数的范围由0到9扩大到0到9999999，这样50
位数最多只用8位，o(8n)与o(n)相差不大。
改进4：
尽管做了3次改进，但空间上还是需要优化(1<=n<=3000000，开不到！)。
我们发现ans[i]=g[i]-g[i-1]，将这个式子拆开，便是：
ans[i] =g[i]-g[i-1] =g[i-1]+g[i|2]-g[i-1] =g[i|2]
而(1<=n<=3000000)，所以我们在做预处理时只要把1500000以内的只求出就行了！
而空间上也只需开一个1..1500000的数组。
经过以上四步改进，最终AC了！
复杂度：
时间复杂度o(n)，空间复杂度o(n)。
疑问：
本人将
f[1]= 1
f[i]= f[k]
进行重新构造后得出了答案，如果用组合数学的方法解此递推式，是否能更好呢？
本人尚不清楚，但本题方法值得一珍藏！
tju1063 硬币
题目:
Problem
我们知道即使是同一种面值的硬币，它们的重量也有可能不一样，因为它受到许
多因素的影响，包括制造工艺和流程上的。
但是任何一种面值的硬币的重量总是处于某个特定范围之内。
现在已知所有面值的硬币的重量范围。给定一堆硬币的总重量，问这堆硬币的总
价值有多少种不同的可能。
举例：已知一角硬币的重量在19到21之间，五角硬币的重量在40到43之间。
有一堆硬币的总重量为99。则它可以由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，最小重量不低于2，最大重量不高于100。最大重量和最小重
量之间的差距不超过30。
Output
每组数据输出仅包括一行表示这堆硬币的总价值有多少种不同的可能性。
Sample Input
99
2
1 19 21
5 40 43
Sample Output
3
算法：
此题的动态规划也不难，构造是关键，我们设：布尔型的f[k,i,j]表示前k项是否有总值为i而总重为j
的可能，那么：
f[0,0,0]= true
f[k,i,j]= f[k,i,j] or f[k-1,i-value,j-weight]
下面就不用再具体说了。。。
tju1077 挑战
题目：
Problem
猫老大认为自己很强，于是找彩虹挑战。彩虹接受了挑战，两人都有一定的血HP1
、HP2。HP1是猫老大的，HP2是彩虹的。他们也有一定攻击力AP1、AP2，AP1是猫
老大的，AP2是彩虹的。当进行攻击时，对方的HP减少自己的攻击力，比如HP1＝2
HP2＝1 AP1＝1
AP2＝1，当彩虹攻击猫老大时，猫老大的HP＝2（HP1）－1（AP2）＝1。现在两个
人对决很多回合，每回合不是猫老大攻击彩虹，就是彩虹攻击猫老大。求猫老大
能赢彩虹的胜率。保留4位小数。
Input
该题含有多组测试数据,每行为HP1,HP2,AP1和AP2 （1<=HP1,HP2,AP1,AP2<=32767
）
Output
每组数据输出一行，为猫老大赢彩虹胜率的值
Sample Input
2 1 1 1
Sample Output
75.0000
算法：
这道题虽然动态规划不完备，但tju上过了。
方程想必人人会列，f[i,j]=0.5*(f[i-1,j]+f[i,j-1])
但动态规划在这题中并不是最好的，更提倡用组合数学里的公式！
疑问：
什么样的公式最好？
tju1078 祝福
题目：
Problem
得知Atlantis即将沉没的消息以后，King决定把他的人民送到安全的国外去
。但是码头已经废弃很多很多年了。码头前有一个迷宫，国王的骑士只身闯入了
这个迷宫……
骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作战，所以很快便招
架不住了，他的大马被打得奄奄一息（。。。）这个时候，迷宫中的两座石像(一
个是猫老大，一个是天使。（！！！！！))里放出了无数锋利的刀片，把不明生
物全部杀死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上多了一个戒
指，上面写着：
“这个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每次移动如果是只要
|x-x1|+|y-y1|<=P(P在输入中给出)，且(x1,
y1)不是障碍物，你就能实现(x, y) -> (x1,
y1)的移动！”(Angel暗自想：还有这么心黑的……)迷宫为n*m的矩阵。骑士从
(n,
m)到(1,
1)。问：在戒指的帮助下，骑士最少要多少步才能回到入口？在步数最少的前提
下，总共有多少种办法到达入口？注意，骑士不会傻到一直停留在原地不动。
Input
该题含有多组测试数据,对于每组数据, 第1行3个整数，n, m,(1<=n,m<=20)和
P(P<=50)，分别代表迷宫大小和移动范围以后n行，每行m个数，代表了迷宫，其
中0代表可通，1代表不能通过。
Output
每组数据输出两个整数，用空格分开，分别代表最少到达入口的步数和路径的数
目。假设一定能够达到入口。
Sample Input
2 2 1
0 0
1 0
Sample Output
2 1
算法：
这题的动态规划有些不同，值得记住。设：f[k,i,j]表示经过k步到达(i,j)的方法总数，可以得到：
f[0,1,1] =1;
f[k,i,j] =Sigma f[k-1,i+a,j+b] (|a|+|b|<=p) 当map[i,j]=0
f[k,i,j] =0 当map[i,j]=1
然后找到最小的k，使得f[k,n,m]>0，输出k,f[k,n,m]即可。
改进：
可以把空间将一维，不过此题数据不大，亦可用3维数组！
复杂度：
时间复杂度为o(n^5)，空间复杂度为o(n^3)或o(n^2)。
tju1017 石子归并
题目：
Problem
你有一堆石头质量分别为W1,W2,W3...WN.(W＜＝100000)现在需要你将石头合并为
两堆，使两堆质量的差为最小。
Input
该程序有多组测试数据，每组测试数据第一行为整数N（1<=N<=20），表示有N堆
石子。接下去N行，为每堆石子的质量。
Output
每组测试数据只需输出合并后两堆的质量差的最小值。
Sample Input
5
5
8
13
27
14
2
4
4
Sample Output
3
0
算法：
这一题看起来必须用搜索算法，其实从数学角度进一步研究可以发现：使得两堆重量最小，即要求合并出重量weight，sum|2-weight最小。于是，此题转化为背包问题了。
先动态规划f[i,j]= f[i,j] or f[i-1,j-Wi]
再循环查找min{weight} f[n,weight]=true，最后输出sum shl 1-weight。
态规划题目总结 by pcpcpc
这是我曾经做过的总结，很值得珍藏！！！
同济大学编程题库动态规划题目总结
作者：pcpcpc
tju1004 防御导弹
题目：
Problem
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系
统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹
都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在
使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
Input
最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000
的正整数）
Output
两个整数M和N。表示：这套系统最多能拦截 M
枚导弹，如果要拦截所有导弹最少要配备 N 套这种导弹系统。
Sample Input
300 250 275 252 200 138 245
Sample Output
5 2
算法：
这道题就是典型的最长单调序列和最长单调序列的覆盖问题，两个问题分别求。
问题一：求最长单调序列的长度。
我们设opt[i]表示从A1到Ai的最长单调序列长度，则：
opt[1]=1
opt[i]=max{opt[k]+1} (1<=k
最后输出opt[n].
问题二：最长单调序列的覆盖个数
我们可以不断求出最长单调序列，把它们从序列集合中删去，直到集合为空集，
在此过程中进行累加。
复杂度：
方法的时间复杂度为o(n^2)，tju1004已经可以Accepted，但是如果n>1000000时
，速度显然不如人意。
改进：
有没有更好的方法呢？当然有！
最长单调序列，顾名思义，单调的，即：A[k]<=(or >= > <)A[i] (k
首先,开一个足够大的数组??A:array[1..maxn]of longint
A[i]表示长度为i的最长单调序列的最后一个数字，程序如下：
procedure main;
var .............
begin
fillchar(a,sizeof(a),0);
ans:=0; {最长单调序列的长}
readln(n);
for s:=1 to n do begin
read(x);
l:=1; r:=ans; {左、右范围}
whlie l<=r do begin {二分}
m:=(l+r) shr 1;
if a[m]<=x then l:=m+1 else r:=m-1;
end;
if l>ans then inc(ans); {新建，即长度为ans+1的最长单调序列出现了！}
a[l]:=x;
end;
end;
最长单调序列的覆盖个数也很好求，只要将if a[m]>=x then l:=m+1 else
r:=m-1中的<=转换为>=即可，其它类似。算法的复杂度显然降低了！
疑问：
为什么只要将if a[m]>=x then l:=m+1 else r:=m-1中的<=转换为>=即可？
tju1039 核电站问题
题目：
Problem
一个核电站有N个放核物质的坑，坑排列在一条直线上。
如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质
。
任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数
Input
该题有多组测试数据，每组数据一行，两个正整数N，M( 1＜N＜50，2≤M≤5)
Output
每组数据只输出一个正整数S，表示方案总数。
Sample Input
4 3
Sample Output
13
算法:
这道题似乎可以用容斥定理来做，但要实现几乎不可能，运算中的数据会很大，
即使高精度也很慢很烦。我们很自然的想到了可以用动态规划算法。
我们开始试探两个元素的dp，设:f[i,j]表示前i个坑放置j个核物质爆炸时的放置
总方案数，那么似乎
f[i,j]= f[i-1,j-1] 当j>0 在第i个坑放核物质
f[i-1,j] 当j=0 不在第i个坑放核物质
但程序编好后,发现结果不对，因为有情况没考虑到??如果在第i个坑放核物质
，那么也许前i-1个坑里j-1个核物质放在最后连续j-1个坑里，在这种情况下在第
i个坑放核物质是不允许的！
我们只好再增加一个参数k,f[i,j,k]表示前i个坑放置j个核物质爆炸且最后连续
放置k个核物质时的放置总方案数，那么
f[i,j,k]= f[i-1,j-1,k-1] 当k>0
最后用个二重循环统计一下，大功告成！
复杂度：
很显然时间复杂度为o(n^3)，空间复杂度为o(n^3)，使用滚动数组可降一维。
疑问：
虽然dp可以通过，但很可能有更好的算法（如公式），目前没有找到，但有一发
现：
Ans(n,m)= 2^n-omega
当n-m不变，omega为常数，问题是omega与n-m到底有什么关系？？
tju1048 Tom的烦恼
题目：
Problem
Tom是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用
有限的资金开了一家汽车零件加工厂，专门为汽车制造商制造零件。由于资金有
限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他
加工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同
厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开
始和结束时间相同不算冲突）。
Tom当然希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件
的加工时间要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有
一台机器），为了赚得尽量多的加工费，Tom不知如何进行取舍。
现在请你帮Tom设计一个程序，合理选择部分（或全部）零件进行加工，使得
得到最大的加工费。
Input
第一行是一个整数m,表示测试数据的个数。
每组测试数据的第一行是一个整数n(n<=30000)，表示共有n个零件须加工。
接下来的n行中，每行有3个整数，分别表示每个零件加工的时间要求。
第一个表示开始时间，第二个表示该零件加工的结束时间，第三个表示加工该零
件可以得到的加工费。
注：数据中的每个数值不会超过100000.
Output
对每组测试数据,输出一个整数，表示Tom可以得到的最大加工费。
Sample Input
1
3
1 3 10
4 6 20
2 5 25
Sample Output
30
算法：
这一题要用动态规划解决。
设：f[i]表示到达时间i时所能得到的最大加工费，则：
f[i]= max{f[k-1]+v[k,i]} (0
[k,i]表示这段时间内的加工费。最后输出f[30000]即可。
改进：
首先，将结束时间作为关键字排序，至于纪录数组a[i]中，以便处理。
随后，在查找是否存在时间(k,i)时只需用一个指针来控制即可。
复杂度：
时间复杂度为o(n^2)，空间复杂度为o(n)，全部数据能在1s内通过！
疑问：
有没有更好的算法呢？
tju1049 砝码问题
题目：
Problem
有一组砝码，重量互不相等，分别为m1、m2、m3……mn；它们可取的最大数量分
别为x1、x2、x3……xn。
现要用这些砝码去称物体的重量,问能称出多少种不同的重量。
Input
第一行为一整数t,表示有t组测试数据。
每组测试数据第一行一个整数n（n<=10），表示有多种不同的砝码；
第二行n个整数（中间用空格分隔），m1、m2、m3……mn，分别表示n个砝码的重
量；（1<=mi<=20）
第三行n个整数（中间用空格分隔），x1、x2、x3……xn，分别表示n个砝码可取
的最大数量。（1<=xi<=20）
Output
每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数
。
注：包括0。
Sample Input
1
2
1 2
2 1
Sample Output
5
算法：
看到这道题很容易联想到典型的背包问题，只是有一点变化。
我们设：布尔型的f[i,j]表示前i个砝码能否称出重量j，则：
f[0,0]:=true
f[i,j]:=f[i,j] or f[i-1,j-k*mi] (1<=k<=xi)
(注意j-k*mi>=0)
最后用个一重循环统计一下f[n,p](0<=p<=maxm)有多少个值为true的即可。
改进：
空间不够时可以用滚动数组来降一维，其实不只如此。
我们不仅要注意到第i个状态只与第i-1个状态有关，还可以发现j-k*mi
复杂度：
经过优化，时间复杂度为o(n^2)，空间复杂度为o(n)，应该比较理想。
tju1050 单词的划分
题目：
Problem
有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将
它划分成若干个部分，每个部分称为一个单词。
出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一
划分工作的。
Input
第一行为一整数T，表示有T组测试数据。
每组测试数据第一行为一字符串。(长度小于256)
第二行为一整数N。（1<=N<=100）
以下N行，每行一个单词。
Output
一个整数，表示字符串可以被划分成的最少的单词数。
Sample Input
1
realityour
5
real
reality
it
your
our
Sample Output
2
算法：
这道题比较容易能想到用dijkstra来求最短路径，有另一种的方法??动态规划
。（其实，这里的动态规划也可以理解为在求最短路径）
首先，用类似邻接矩阵的布尔型的l[i,j]表示从i到j是不是单词。设：f[i]表示
前i个串能分成的最少单词数，很简单地得到：
f[0]= 0
f[i]= min{f[k]+1} (0<=k
改进：
我们可以像tju1048 Tom的烦恼那样，先排一下序再dp。想必不用具体阐述了。
复杂度：
经过优化的时间复杂度为o(n^2)，可以Accepted。
tju1059 数的计数
题目：
Problem
先输入一个自然数n(n≤3000000)，然后对此自然数按照如下方法进行处理
1?不作任何处理:
2?在它的左边加上一个自然数，但该自然数不能超过原数的一半;
3?加上数后，继续按此规则进行处理，直到不能再而 自然数为止。
例如n=6
6
16
26
126
36
136
所以满足要求的个数为6。
Input
包含多个测试数据,每行是一个整数n(1<=n<=3000000)
Output
一个整数,表示解的个数(保证不超过50位)
Sample Input
6
Sample Output
6
算法：
这道题在许多书上都有介绍，我们设：
f[i]表示i个数的答案，则：
f[1]= 1
f[i]=
改进1：
算法虽然经典，但时间复杂度为o(n^2)，如此大的数据显然要超时，能不能降低
一维呢？
换一种构造就行了！
假如我们设g[i]表示f[1]到f[i]总和，那么
g[1] =1
g[i] =g[i-1]+g[i|2]
时间复杂度降到了1维！
ans[1]= 1
ans[i]= g[i]-g[i-1]
改进2：
我们不难看出，在解出g[i]后，g[k](1<=k
开头做一下预处理，这是极大的优化！
改进3：
尽管时间降低到一维，但数据很大(保证不超过50位)!
于是我们不得不用高精度运算，但如果这样，时间复杂度不就又重返二维了吗？
可以用压缩数组来避免。即：每一位数的范围由0到9扩大到0到9999999，这样50
位数最多只用8位，o(8n)与o(n)相差不大。
改进4：
尽管做了3次改进，但空间上还是需要优化(1<=n<=3000000，开不到！)。
我们发现ans[i]=g[i]-g[i-1]，将这个式子拆开，便是：
ans[i] =g[i]-g[i-1] =g[i-1]+g[i|2]-g[i-1] =g[i|2]
而(1<=n<=3000000)，所以我们在做预处理时只要把1500000以内的只求出就行了！
而空间上也只需开一个1..1500000的数组。
经过以上四步改进，最终AC了！
复杂度：
时间复杂度o(n)，空间复杂度o(n)。
疑问：
本人将
f[1]= 1
f[i]=
进行重新构造后得出了答案，如果用组合数学的方法解此递推式，是否能更好呢？
本人尚不清楚，但本题方法值得一珍藏！
tju1063 硬币
题目:
Problem
我们知道即使是同一种面值的硬币，它们的重量也有可能不一样，因为它受到许
多因素的影响，包括制造工艺和流程上的。
但是任何一种面值的硬币的重量总是处于某个特定范围之内。
现在已知所有面值的硬币的重量范围。给定一堆硬币的总重量，问这堆硬币的总
价值有多少种不同的可能。
举例：已知一角硬币的重量在19到21之间，五角硬币的重量在40到43之间。
有一堆硬币的总重量为99。则它可以由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，最小重量不低于2，最大重量不高于100。最大重量和最小重
量之间的差距不超过30。
Output
每组数据输出仅包括一行表示这堆硬币的总价值有多少种不同的可能性。
Sample Input
99
2
1 19 21
5 40 43
Sample Output
3
算法：
此题的动态规划也不难，构造是关键，我们设：布尔型的f[k,i,j]表示前k项是否有总值为i而总重为j
的可能，那么：
f[0,0,0]= true
f[k,i,j]= f[k,i,j] or f[k-1,i-value,j-weight]
下面就不用再具体说了。。。
tju1077 挑战
题目：
Problem
猫老大认为自己很强，于是找彩虹挑战。彩虹接受了挑战，两人都有一定的血HP1
、HP2。HP1是猫老大的，HP2是彩虹的。他们也有一定攻击力AP1、AP2，AP1是猫
老大的，AP2是彩虹的。当进行攻击时，对方的HP减少自己的攻击力，比如HP1＝2
HP2＝1 AP1＝1
AP2＝1，当彩虹攻击猫老大时，猫老大的HP＝2（HP1）－1（AP2）＝1。现在两个
人对决很多回合，每回合不是猫老大攻击彩虹，就是彩虹攻击猫老大。求猫老大
能赢彩虹的胜率。保留4位小数。
Input
该题含有多组测试数据,每行为HP1,HP2,AP1和AP2 （1<=HP1,HP2,AP1,AP2<=32767
）
Output
每组数据输出一行，为猫老大赢彩虹胜率的值
Sample Input
2 1 1 1
Sample Output
75.0000
算法：
这道题虽然动态规划不完备，但tju上过了。
方程想必人人会列，f[i,j]=0.5*(f[i-1,j]+f[i,j-1])
但动态规划在这题中并不是最好的，更提倡用组合数学里的公式！
疑问：
什么样的公式最好？
tju1078 祝福
题目：
Problem
得知Atlantis即将沉没的消息以后，King决定把他的人民送到安全的国外去
。但是码头已经废弃很多很多年了。码头前有一个迷宫，国王的骑士只身闯入了
这个迷宫……
骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作战，所以很快便招
架不住了，他的大马被打得奄奄一息（。。。）这个时候，迷宫中的两座石像(一
个是猫老大，一个是天使。（！！！！！))里放出了无数锋利的刀片，把不明生
物全部杀死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上多了一个戒
指，上面写着：
“这个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每次移动如果是只要
|x-x1|+|y-y1|<=P(P在输入中给出)，且(x1,
y1)不是障碍物，你就能实现(x, y) -> (x1,
y1)的移动！”(Angel暗自想：还有这么心黑的……)迷宫为n*m的矩阵。骑士从
(n,
m)到(1,
1)。问：在戒指的帮助下，骑士最少要多少步才能回到入口？在步数最少的前提
下，总共有多少种办法到达入口？注意，骑士不会傻到一直停留在原地不动。
Input
该题含有多组测试数据,对于每组数据, 第1行3个整数，n, m,(1<=n,m<=20)和
P(P<=50)，分别代表迷宫大小和移动范围以后n行，每行m个数，代表了迷宫，其
中0代表可通，1代表不能通过。
Output
每组数据输出两个整数，用空格分开，分别代表最少到达入口的步数和路径的数
目。假设一定能够达到入口。
Sample Input
2 2 1
0 0
1 0
Sample Output
2 1
算法：
这题的动态规划有些不同，值得记住。设：f[k,i,j]表示经过k步到达(i,j)的方法总数，可以得到：
f[0,1,1] =1;
f[k,i,j] =Sigma f[k-1,i+a,j+b] (|a|+|b|<=p) 当map[i,j]=0
f[k,i,j] =0 当map[i,j]=1
然后找到最小的k，使得f[k,n,m]>0，输出k,f[k,n,m]即可。
改进：
可以把空间将一维，不过此题数据不大，亦可用3维数组！
复杂度：
时间复杂度为o(n^5)，空间复杂度为o(n^3)或o(n^2)。
tju1017 石子归并
题目：
Problem
你有一堆石头质量分别为W1,W2,W3...WN.(W＜＝100000)现在需要你将石头合并为
两堆，使两堆质量的差为最小。
Input
该程序有多组测试数据，每组测试数据第一行为整数N（1<=N<=20），表示有N堆
石子。接下去N行，为每堆石子的质量。
Output
每组测试数据只需输出合并后两堆的质量差的最小值。
Sample Input
5
5
8
13
27
14
2
4
4
Sample Output
3
0
算法：
这一题看起来必须用搜索算法，其实从数学角度进一步研究可以发现：使得两堆重量最小，即要求合并出重量weight，sum|2-weight最小。于是，此题转化为背包问题了。
先动态规划f[i,j]= f[i,j] or f[i-1,j-Wi]
再循环查找min{weight} f[n,weight]=true，最后输出sum shl 1-weight。
2006/10/04
‘天使的施舍’的CODE
different kisses
