noip教程动态规划.pptxVIP

为了解决一类最优化问题 通过求得所有子问题的最优解来得到最终问题的最优解;状态 状态转移方程 初始条件 ;线性动态规划 区间动态规划 状态压缩动态规划 树形动态规划;状态是一维的 F[i] 由 F[j] (ji) 得到 初始条件 F[0] 或 F[1];设有整数序列b1,b2,b3,…,bm，若存在下标i1i2i3 …in，且bi1bi2bi3 …bin，则称 b1,b2,b3,…,bm中有长度为n的上升序列bi1 , bi2 ,bi3 ,…,bin 。 求最长上升序列的长度N 求长度为N的上升序列的个数 求本质不同的长度为N的上升序列的个数 N=1000;状态：F[i]表示以b[i]结尾的最长上升序列长度 转移方程：F[i]=max(F[j]+1),jI,b[j]b[i] 初始条件：F[i]=1, 1=i=N T[i]表示以b[i]结尾的序列长度为F[i]的方案数 T[i]=sigma(T[j]), F[i]=F[j]+1, B[i]B[j] 初始条件：T[i]=1;本质不同？ Order[i]表示B[i]在序列B中是第几大的 T[i]=sigma(T[j]), 当某个order[j1]=order[j2]时，只累加一个 时间复杂度：O(N^2) 空间复杂度：O(N);P[i] 表示上身序列长度为i的序列末尾元素的最小值 当计算F[i]时，二分j，满足P[j]B[i] F[i]=F[j]+1 P[F[i]]=min(P[F[i]], B[i]) 时间复杂度：O(NlogN);考虑一个由N个整数构成的数列，其中1到N都在数列中出现了恰好一次。 在这个数列中从左到右任取两个数，如果前者比后者大，那么这对数就是一个逆序对。而整个数列的逆序数就是其中所有逆序对的总数。例如，数列（1，4，3，2）的逆序数为3，因为存在三个逆序对：（4，3），（4，2）和（3，2）。 写一个程序，计算有多少长度为N的这种数列，使它的逆序数恰为C。 N=1000,C=10000;状态：F[i][j]表示1～i的一个排列，逆序对数目为j的方案数 枚举1的位置 F[i][j]=sigma(F[i-1][j-k]),0=k=i-1 时间复杂度：O(N*N*C) 空间复杂度：O(N*C) ?;F[i][j]=F[i][j-1]+F[i-1][j]-F[i-1][j-i] 第i阶段只与第i-1阶段有关 滚动数组，省掉一维 时间复杂度：O(N*C) 空间复杂度：O(C);如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以4的余数最小。 ;状态：F[i]表示到点i的最小值 转移：F[i]=min((F[j]+num[i]) mod 4),j到i有边 样例就出现bug ?;局部???优解不能保证全局最优解 本题不符合最优化性质 F[i][j] 表示到点i余数为j是否可行 求出所有x=(F[k][p]+num[i])%4,F[i][x]=true;DP不可滥用 用之前先考虑是否符合最优化原理，并且没有后效性 确定了是DP之后考虑三个基本要素;状态有两维或者多维 F[i][j]表示i~j这个区间的最优值 F[i-1][j],F[i][j-1] ? F[i][j] F[i][k] + F[k][j] ? F[i][j] ;在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20), (1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少 (2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大 ;;贪心;用data[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] = 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(N^2);在一条马路上，有一排灯，一个小朋友要去关灯，如果灯没有被关掉，就会每秒造成一定的损失。小朋友一开始在某一个位置，在他左边和右边分别有一些灯，给出这些灯和他的距离以及每个灯每秒会造成的损失，求一个方案使得损失最小，输出最小损失。灯的个数=1000 ;关掉的灯一定是一个连续的区间 如果路过一个灯但是没有去关掉它…… 设 opt[i][j][0/1] 表示区间[i,j]中的灯都被关掉