动态acm新手该看看的dp

1、动态规划Dynamic Programming唐陈兴2007.12.30动态规划的基本思想动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重

2、复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。动态规划法一般步骤1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；4、根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。动态规划问题的

3、特征动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。从一个简单的问题入手FOJ1004 Number Triangle求人从顶端到底部,每次只能向左下右下走,最多能取得的值.数据规模: 行数1=R=1000 数塔中数值0.100如图最优解为

4、 7-3-8-7-5 =30从一个简单的问题入手状态表示 用aij表示第i行第j列的值。 用F(i,j)表示第i行第j列走到底部所能取得的最大值。而F(1,1)就是题目所求的答案。搜索源代码#includeconst int M=1000+5;int aMM,n;inline int max(int x,int y) return xy?y:x; int f(int i,int j) if (i=n) return aij; else return aij+max(f(i+1,j),f(i+1,j+1); int main() int i,j; while(scanf(%d,&n)=1) fo

5、r(i=1;i=n;i+) for(j=1;j=i;j+) scanf(%d,&aij); printf(%dn,f(1,1); return 0; 从一个简单的问题入手人每次从顶部往下走，都有2种选择。如果搜索，到第n层的搜索量为为2n。1=n=1000，这种搜索量是从时间角度无法接受的。细心观察，不难发现实际上做了很多重复的搜索。用动态规划思想解决减少重复计算：自底向上。状态表示 用aij表示第i行第j列的值。 用Fij表示第i行第j列走到底部所能取得的最大值。而F11就是题目所求的答案。状态转移Fij=aij+max(Fi+1j,Fi+1j+1) 动态规划源代码#includeconst

6、 int M=1000+5;int fMM,aMM;inline int max(int x,int y) return xy?y:x; int main() int i,j,n; while(scanf(%d,&n)=1) for(i=1;i=n;i+) for(j=1;j=i;j+) scanf(%d,&aij); for(j=1;j=1;i-) for(j=1;j=i;j+) fij=aij+max(fi+1j,fi+1j+1); printf(%dn,f11); return 0;记忆化搜索记忆化搜索：算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。一般

7、说来，动态规划总要遍历所有的状态，而搜索可以排除一些无效状态。更重要的是搜索还可以剪枝，可能剪去大量不必要的状态，因此在空间开销上往往比动态规划要低很多。记忆化算法在求解的时候还是按着自顶向下的顺序，但是每求解一个状态，就将它的解保存下来，以后再次遇到这个状态的时候，就不必重新求解了。这种方法综合了搜索和动态规划两方面的优点，因而还是很有实用价值的。 记忆化搜索动态规划不仅需要推出状态转移方程式，还要进行拓扑排序。搜索相对于动态规划最大的劣势无非就是重复计算子结构，所以我们在搜索的过程中，对于每一个子结构只计算一次，之后保存到数组里，以后要用到的时候直接调用就可以了。记忆化搜索的实质是动态规划

8、,效率也和动态规划接近，形式是搜索,简单直观，代码也容易编写，不需要进行什么拓扑排序了。可以归纳为：记忆化搜索=搜索的形式+动态规划的思想数塔记忆化搜索源代码#include#includeconst int M=1000+5;int aMM,n, ff MM;inline int max(int x,int y) return xy?y:x; int f(int i,int j) if (ffij!=-1) return ffij; if (i=n) return aij; else return ffij=aij+max(f(i+1,j),f(i+1,j+1); int main() in

9、t i,j; while(scanf(%d,&n)=1) for(i=1;i=n;i+) for(j=1;j=i;j+) scanf(%d,&aij); memset(ff,-1,sizeof(ff); printf(%dn,f(1,1); return 0;FOJ1320 Ones给一个整数n，要你找一个值为n的表达式，这个表达式只有1 + * ( ) 够成。并且1不能连续，比如11+1就不合法。输入n,(1=n=10000)输出最少需要多少个1才能构成表达式。样例：n=2=1+1 ans=2 n=10=(1+1)*(1+1+1+1+1) ans=7Ones让fi表示最少数量的1能够表示i。

10、add: fi=fj+fi-j 0jimultiply: fi=fj+fi/j 0ji, i%j=0for(i=1;i=n;i+) fi=i; for(j=1;ji;j+) fi=min(fi,fj+fi-j); if (i%j=0) fi=min(fj+fi-j); O(n2) n=10000OnesHow to improve?For multiply, 1j*ji.fi=minfj+fi/j+fi%j 1j*jiO(n1.5) 1=n=10000n1.5=1,000,000 算法时间可以以计算机每秒执行8,000,000语句进行估算。Ones源代码#include #includeint

11、 f10001;int main() int i,j,tmp,r; for(i=1;i=10000;i+) r=sqrt(i); fi=i; for(j=2;j=r;j+) tmp=fi%j+fj+fi/j; if(tmpfi) fi=tmp; while(scanf(%d,&i)!=EOF) printf(%dn,fi); return 0;FOJ1319 Blocks of Stones 经典的石子归并问题有n (1=n7 1-8 分数7+8=15合并方案二: 2 5 1-2 6-8 分数6+8=14FOJ1319 Blocks of Stones状态表示：用ai 表示初始时每堆石子的个数

12、。用si表示初始时从第1堆到第i堆石子的总和。用fij(i=j)表示从第i堆合并到第j堆的最小分数。fij=minfi,k-1+fk,j+wi,j;wij=sumaiaj=sj-si-1;这样枚举是n3的。FOJ1319 Blocks of Stonesfij=minfi,k-1+fk,j+wi,j;改进k的取值范围： Let s(i,j)=maxk|arg minfi,j s(i,j-1)=k=s(i+1,j) O(n2)FOJ1319 Blocks of Stones 另外，FOJ1319可以交换任意两个相邻的石堆，这步可以通过O(n)的枚举来实现。FOJ1348 Longest Orde

13、red Subsequence 最长递增子序列给一个序列，求它的一个最长递增子序列。递增序列满足：a1 a2 . aN 例如序列(1, 7, 3, 5, 9, 4, 8) 的递增子序列有 (1, 7), (3, 4, 8) (1,3,4,8) 其中(1,3,4,8)为最长递增子序列。求给定的序列中最长递增子序列的长度。（最长递增子序列未必唯一）O(n2)设fi表示：序列L中以ai为末元素的最长递增子序列的长度。在求以ai为末元素的最长递增子序列时，找到所有序号在序列L前面且小于ai的元素aj，即ji且ajai。如果这样的元素存在，那么对所有aj,都有一个以aj为末元素的最长递增子序列的长度fj

14、，把其中最大的fj选出来，那么fi就等于最大的fj加上1，即以ai为末元素的最长递增子序列，等于以使fj最大的那个aj为末元素的递增子序列最末再加上ai；如果这样的元素不存在，那么ai自身构成一个长度为1的以ai为末元素的递增子序列。 样例说明：ai= 1, 7, 3, 5, 9, 4, 8fi= x, x, x, x, x, x, 1fi= x, x, x, x, x, 2, 1fi= x, x, x, x, 1, 2, 1fi= x, x, x, 2, 1, 2, 1fi= x, x, 3, 2, 1, 2, 1fi= x, 2, 3, 2, 1, 2, 1fi= 4, 2, 3, 2,

15、1, 2, 1#includeint main() int i,j,n,a1001,f1001,ans; while(scanf(%d,&n)!=EOF) for(i=1;i=1;i-) fi=1; for(j=i+1;j=n;j+) if (aiaj & fifj+1) fi=fj+1; ans=0; for(i=1;i=n;i+) if (ansfi) ans=fi; printf(%dn,ans); return 0;O(n*log(n)对算法的改进在上述算法中，在计算每一个fi时，都要找出最大的fj(ji)来，由于fj没有顺序，只能顺序查找满足ajai最大的fj，如果能将让fj有序，就

16、可以使用二分查找，这样算法的时间复杂度就可能降到O(nlogn)。于是想到用一个数组b来存储“子序列的”最大递增子序列的最末元素，即有bfj = aj在计算fi时，在数组b中用二分查找法找到满足ji且bfj=ajai的最大的j,并将bfj+1置为ai样例说明：ai= 1, 7, 3, 5, 9, 4, 8b=1b=1,7b=1,3b=1,3,5b=1,3,5,9b=1,3,4,9b=1,3,4,8/LIS 最长递增序列n*log(n)int LIS (int *a,int n)int ans,i,k,*b=new int n+1;bans=0=-0 x7fffffff;for(i=0;ians

17、) b+ans=ai; else if (bkai) bk=ai;delete b; return ans;源代码FOJ1147 Tiling In how many ways can you tile a 2 x n rectangle by 2 x 1 or 2 x 2 tiles? Here is a sample tiling of a 2 x 17 rectangle. Input is a sequence of lines, each line containing an integer number 0 = n = 250. For each line of input, ou

18、tput one integer number in a separate line giving the number of possible tilings of a 2xn rectangle. 状态表示：Fn表示2 x n的走道上铺满1 x 2， 2 x 2 的砖块的方法数量考虑最后一块砖和最后两块砖的放法，很容易写出DP状态转移方程。Fi=Fi-1+Fi-2+Fi-2, 边界：F0=F1=1;最后一块1 x 2竖放:Fi-1最后两块1 x 2横放:Fi-2最后放一块 2 x 2的:Fi-2另外： n = 250，需要高精度FOJ1342 Tight Words Given is an

19、 alphabet 0, 1, . , k, 0 = k = 9 . We say that a word of length n over this alphabet is tight if any two neighbour digits in the word do not differ by more than 1. Input is a sequence of lines, each line contains two integer numbers k and n, 1 = n = 100. For each line of input, output the percentage

20、 of tight words of length n over the alphabet 0, 1, . , k with 5 fractional digits. FOJ1342 Tight Words紧密单词：单词中任何相邻位置的数字相差不超过1。长度为n，由0.k组成的单词中，紧密单词的百分比。(1=n=100，0=k=9)例如k=2, n=2 的单词共有(k+1)n=32=9个。其中紧密单词有7个：00,01,10,11,12,21,22非紧密单词有2个：02,20百分比为7/9=77.77778%FOJ1342 Tight Words长度为n，由0.k组成的单词共有(k+1)n 个

21、，(1=n=100，0=k=9)。枚举所有的单词显然是不可能的。 O(k+1)*n)空间，O(k+1)*n)时间在使用数字0.k构造单词的条件下，Fij表示单词长度为i,以数字j为基本单词产生的紧密单词的百分比。Fi0=(Fi-1j+Fi-1j+1)/(k+1);Fij=(Fi-1j-1+Fi-1j+Fi-1j+1)/(k+1);Fik=(Fi-1j-1+Fi-1j+1)/(k+1);#include #include double f10010; double tot;int main() int i,j,k,n; while (scanf(%d %d,&k,&n)!=EOF) k+; me

22、mset(f,0,sizeof(f); for (i=0;ik;i+) f0i=100.0/k; for (i=1;in;i+) fi0=fi-10/k; for (j=1;jk;j+) fij+=(fi-1j+fi-1j-1)/k; for (j=0;jk-1;j+) fij+=fi-1j+1/k; tot=0; for (i=0;i1)，则由长度为n-1的概率添加头尾得到 tmp0=(f0+f1)/(k+1);tmpi=(fi-1+fi+fi+1)/(k+1);tmpk=(fk-1+fk)/(k+1);memcpy(f,tmp,sizeof(double)*(k+1);for(ans=0.

23、0,i=0;i=k;i+) ans+=fi; #include stdio.hint main()double f10,temp10,ans;int k,n,i,t; while(scanf(%d%d,&k,&n)!=EOF) for(i=0;i=k;i+) fi=100.0/(k+1);for(t=2;t=n;t+) temp0=(f0+f1)/(k+1); for(i=1;i=k-1;i+) tempi=(fi-1+fi+fi+1)/(k+1); tempk=(fk-1+fk)/(k+1); for(i=0;i=k;i+) fi=tempi;for(ans=0.0,i=0;i=k;i+)

24、ans+=fi;printf(%0.5lfn,ans);return 0;FOJ1559 Count Zeros 正整数可以表示为2进制。计算1.2n中，这些正整数以2进制表示时共有多少个0. (1=n111的过程，而10000还有右数第4的1没有被计算过，所以结果还要加1。FOJ1523 A Version of Nim 可以用DP解决的一类博弈问题问题描述: 有4堆石子每堆最多9个，2个人轮流取石子，每次可以且必须取其中1堆的1-3个石子，取得最后一个石子的人失败，假设双方都采用最优策略，问先手胜败。局面必败局：无论如何取石子，其子状态都是必胜局。必胜局：存在一种或一种以上的取法，使得其子

25、状态为必败局。对于本题，典型的必败局有(1,0,0,0),(5,0,0,0) 必胜局有(2,0,0,0),(3,0,0,0),(4,0,0,0),(1,1,0,0)FOJ1523 A Version of Nim四堆石子(x,y,i,j)Fxyij=1表示先手必胜，0表示先手必败。if (x=0 & y=0 & i=0 & j=0) Fijxy=1; if (!ff(i-1,j,x,y) | !ff(i-2,j,x,y) | !ff(i-3,j,x,y)| !ff(i,j-1,x,y) | !ff(i,j-2,x,y) | !ff(i,j-3,x,y)| !ff(i,j,x-1,y) | !f

26、f(i,j,x-2,y) | !ff(i,j,x-3,y)| !ff(i,j,x,y-1) | !ff(i,j,x,y-2) | !ff(i,j,x,y-3) Fijxy=1;else Fijxy=0;int ff(int i,int j,int x,int y)if (i0 | j0 | x0 | y0) return 1;else return fijxy;FOJ1381 Regular ExpressionsYou are given two regular expressions R1 and R2 and should find minimal string S matching both. String consists of capi