2019第三次动态规划训练

概述

• 本次训练于 2019-11-3 星期日 举行
• 主题为动态规划
• 主讲人: 李济升

教案下载

点此下载

简单dp简单题解

樱花

由于是几个背包的混合，有个最直接的办法就是按照可以观看的次数进行不同的状态转移，而另一个比较精巧的方法是把一个物品按照二进制分成不同的物品，然后按照 01 包做

导弹拦截

这里就是想让用 dp 的方法，$latex O(n^2)$ 的方法找最长不递增子序列以及个数，拿满分得别的办法

金明的预算方案

依赖背包，状态转移的时候多一个选择，有附件的物品可以选择拿或者不拿附件

模板题

$latex dp[i][j]$ 表示第一列的\(i\)和第二列的\(j\)为结尾的时候最长公共子序列为多长，然后构造状态转移

疯狂的采药

完全包

采药

01包

Views: 98