动态规划基础和建模.ppt

给定一个DAG，求从s到t的最长路 关键路径 设f[i]表示从s到i的最长路径 F[i]+dis[i][j]-f[j] 拓扑排序的过程中解决 关键路径 给定一个图，边有的是单向的，有的是双向的 有一个水晶球，每个点有一个价格 从s出发到t，沿途在某个点买入水晶球，在另一个点卖出 显然你要先买入才能卖出 最大化收益 最优贸易（NOIP2009T） 方法一： 同一个SCC里的点都可以走到，可以在其中任意一个买，任意一个卖 收缩SCC，记录SCC的最大值和最小值 F[i]表示到i的最大获利，g[i]表示到i的最小价格，minv[i]表示i所在SCC的最小价格，maxv[i]表示i所在SCC的最大价格 G[i]=min{g[j],minv[i]} F[i]=max{f[j],maxv[i]-g[i]} 边拓扑排序边做 最优贸易 方法二： F[i][0]表示到i点，没有水晶球的最大 F[i][1]表示到i点，有水晶球的最大 F[i][0]=max{f[j][0],f[j][1]+w[i]} f[i][1]=max{f[j][1],-w[i]} 前面说过：动态规划是状态图的最短路或最长路 嵌套在SPFA算法中，迭代求解 最优贸易 这类问题在NOIP中一般不会出现，但鉴于在NOIP的模拟题和WFTSC中出现了不止一次，稍微提一下 插头DP 棋盘DP 集合DP 状态压缩模型 把问题的状态压缩成一个k进制数来表示，利用这个数的每一位反映出来的信息来进行转移 问题规模往往特别小 状态压缩模型 困惑的旅行家（WFTSC2010T） 经典的TSP问题 最优哈密顿回路 设f[i][S]表示当前在i点，经过的点的集合是S F[i][S]=min{f[j][S-{i}]+dis[j][i]} Ans=min{f[i][2^n-1]+dis[i][1]} 困惑的旅行家 多线程动态规划，顾名思义，就是很多条线一起进行的动态规划。这类问题要完整的表达出各条线的特点，转移往往比较简单。 多线程动态规划 一个公司有三个移动服务员。如果某个地方有一个请求，某个员工必须赶到那个地方去（那个地方没有其他员工），某一时刻只有一个员工能移动。被请求后，他才能移动，不允许在同样的位置出现两个员工。从p到q移动一个员工，需要花费c(p,q)。这个函数没有必要对称，但是c(p,p)=0。公司必须满足所有 的请求。目标是最小化公司花费。 Mobile Service（tyvj1061） F[a][b][c]表示三个员工分别在a,b,c位置上 F[a][b][c]-f[q][b][c]+c[a][q] -f[a][q][c]+c[b][q] -f[a][b][q]+c[c][q] F[1][2][3]=0 Mobile Service 你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。每个城市只能访问一次，除了旅行开始的城市之外，这个城市必定要被访问两次（在旅行的开始和结束）。你不允许使用其他公司的航线或者用其他的交通工具。 给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。 Canada Tour（USACO Training） 按照东西方向排序 设第一条线到i，第二条线到j 因为两条线可以交换，我们限定ij F[i][j]=max{f[i’][j], f[i][j’], j’i f[j’][i], j’I}+1 时间复杂度O(n^2m) Canada Tour 多重动态规划就是DP套DP 一般方法是从外到内，一层层的分析 多重动态规划 谢谢！ 邮箱：clavichord93@ QQ：381352239 欢迎骚扰 MM优先 贪吃的九头龙 我们从多叉转二叉的角度来看这道题 贪吃的九头龙 给定一棵树，求树的最长链 树的最长链 贪心做法：两次BFS 证明 树的最长链 动态规划：设f[i]表示儿子连上来的最长链，g[i]表示儿子连上来的次长链，h[i]表示父亲来的最长链 F[i]=max{f[j]}+1 同时更新g[i] H[i]=max{f[p],h[p]}+1,f[p]f[i]+1 =max{g[p],h[p]}+1,f[p]=f[i]+1 树的最长链 给定一棵树，求树的最小点支配集。 N=10000