动态规划基础和建模.pptxVIP

动态规划基础和建模;动态规划是统筹学的重要内容 动态规划是OI的重要内容 据不完全统计，每次考试动态规划起码有一道题 ;这个课件的目的： 对动态规划的模型进行了一些总结 有部分内容超出了NOIP范围 为同学们提供一个刷题的方向 请同学们踊跃发言;阶段 状态 决策 状态转移 状态转移方程;最优子结构 无后效性原则 重叠子问题;拓展一下： 阶段 - 拓扑序 状态 - 点 状态转移 - 边 决策 - 前驱？DFA？;实现方式： 递推：顺推和逆推 记忆化有哪些信誉好的足球投注网站 前者灵活，优化方法多 后者可以减少不必要节点的计算;时间复杂度： 状态数*转移费用;线性模型 区间模型 矩形模型 树形模型 背包模型 图状模型 SCDP 多线程DP 多重DP 更广泛的;单线问题： 上楼梯问题 LIS问题 乌龟棋 诗人小G（简化版） 双线问题： LCS问题 模糊匹配;Zbwmqlw神犇要上楼梯，他一次可以上一层，也可以上两层。 楼梯有n层 有多少种上楼梯的方案;N=10^7？ 设f[i]表示到第i层得方案数 前一步可以上一层也可以上两层 F[i]=f[i-1]+f[i-2] N=10^15？ 矩阵乘法 ;给定一个数列{an}，求它的一个子序列{bm} 满足b1b2b3…bm 使得m最大 N=10000;设f[i]表示以i结尾的LIS的长度 F[i]=max{f[j]}+1,ji且a[j]a[i] 时间复杂度？O(n^2) 如何优化？;对于i来说，如果存在一个长度为len的LIS以i结尾，那么也一定存在长度len的 即：满足单调性！ 设g[i]表示f[j]=i的最小的a[j] 二分g[k]=a[i]的最大的k F[i]=k+1 时间复杂度O(nlogn);?;F[i][a][b][c][d]表示到位置i，四种操作分别进行了a,b,c,d次 决策有四种 时间复杂度：O(nc^4) TLE+MLE;?;一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行???准长度差值绝对值的P 次方，而一个排版的不协调度为所有行不协调度的总和。 小G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。;F[i]表示前i句诗的最小不协调度 F[i]=min{f[j]+(sum[i]-sum[j]+i-j-L)^p} 时间复杂度O(n^2) 优化？ 导数证明四边形不等式，有兴趣的同学自己查阅有关资料;给定两个字符串s，t 求最长公共字串 例：abcde和ace的LCS是ace N=1000;设f[i][j]表示第一个串到i，第二个串到j的LCS F[i][j]=f[i-1][j-1]+1, s[i]=t[j] =min{f[i-1][j],f[i][j-1]}, s[i]!=t[j] 时间复杂度O(n^2);给定两个字符串s和t，每个字符串有英文字母和*？！组成，*？！的含义分别是： *：匹配一个或多个字符； ？：匹配至少一个至多三个字符； ！：匹配至少三个字符。 问两个字符串是否能够匹配。 N=1000;?;石子归并 回文词 决斗问题 Blocks;有n堆石子，第i堆重a[i] 每次可以合并相邻两堆 合并费用为新堆的重量 求合并成一堆的最小费用 N=200;合并的费用是一段的和 设f[i][j]表示合并i到j的一段 F[i][j]=min{f[i][k]+f[k+1][j]}+sum[i][j] 时间复杂度O(n^3);给定一个字符串s，要求添加最少的字符，使得s成为一个回文串。 N=5000;abcba：回文 abcbc：不回文 F[i][j]表示i到j变成回文的最小代价 F[i][j]=f[i+1][j-1], s[i]=s[j] =min{f[i+1][j],f[i][j-1]}+1, s[i]!=s[j] 时间复杂度O(n^2);N个人排成一圈，他们要决斗N-1场，其中相邻的两人决斗（即第i个人与第i+1个人决斗，第N个人与第1个人决斗），死者退出，最终剩下的人胜利。将任意两个人之间决斗的输赢情况告诉你，决斗顺序由你安排，问哪些人可能成为最终的胜利者？ N=200;首先把环复制一份接到后面 然后一个人获胜就是跟自己相遇 Meet[i][j]表示i能j相遇 Meet[i][j]=meet[i][k]