JZYZ-DP刷题柱

发表于 | 阅读次数:
字数统计: 1,817 字

刷题柱

  1. p1253 经典问题
  2. p1254 经典问题 LIS + Dilworth定理 ：偏序集的最少反链划分数等于最长链的长度
  3. p1255 经典问题 预处理正反各求一遍 LIS 枚举每一个点处理答案
  4. p1256 经典问题 先按照时间顺序进行排序， 判断第 i 个苹果之前的苹果是否可以接到， 然后更新 f 值即可

  1. p1257 经典问题 按照 C 城市的坐标排序， 然后枚举第 i 城市， 如果第 i 个城市之前的航线可以建造， 那么更新 f 的值

  2. p1258 简单题 记忆化搜索或者 DP 都行 f[i] = min(f[i], f[i-j] + a[j]) (0<= j <=min(10, i))

  3. p1259 简单题 按照每个左区间的值进行排序，枚举每个区间 i ， 找在 i 之前的区间中不与 i 区间相交的一个最大 f 值来更新 f[i]

  4. p1263 简单题 f[i][j] 表示前 i 个公司所能得到的最大利润， f[i][j] = max(f[i][j], f[i-1][k] + a[i][j-k])(0<=k<j) f[i-1][k] + a[i][j-k]这个表示第 i 个公司得到 j-k 件设备， 价值为a[i][j-k]， 再加上 i-1 个公司获得的 k 个设备的价值之和

  5. p1264 简单题 需要先预处理出一个 sum 数组来快速的计算出第 i 个到 第 j 个书稿的总页数， f[i][j] 用来表示前 i 个人 抄写 j 本书稿花费的最长时间， 枚举 k 的作用是把 k+1 到 j 这几本书给 i 抄， 求出 f 数组之后， 进行递归输出分配的方案即可， 用到了贪心的方法

  6. p1266 一道比较NB的题， 由于这道题不满足最优子结构的特性， 所以没法使用动态规划， 但是可以把这道题转化成 判定性问题来求解c[i][j]表示的是 前 i 个人达到 j 的重量是否可能，转移方程可以写为 c[j][k] = c[j-1][k-w[i]] | | c[j][k](1<= j <=i, w[i]<= k <=sumw)， 边界条件是 c[0][0] = true，这样一来， 就可以把所有的 n 个人是否能达到 k 的重量的问题解决掉了。
    关于最终题设所要求的答案， 可以从 n/2 这个人的状态中寻找答案， 从f[mid][sumw/2] 开始向 sumw/2 的两头寻找， 如果出现这样的值，既满足两个组内所有人的重量加起来最接近。退出循环输出即可。

  7. p1267 简单题 可以设计阶段为每个任务， 先按照每个任务开始的时间排序， 到网上找了一下题解，发现好像做这道题的思路好像都不太相同， 有好多设计的状态是时间， 并且好像使用了倒推这种神奇操作，找到了一个思路和我相同的题解挂在这里 链接 大致思路和那种选择区间并且不能重合的题差不多， 不过需要多考虑一些东西， 来维护更多的状态来作为状态转移时的依据。

  8. p1269 简单题 还是需要维护的状态多了一些， 其他的很普通？ 这种题还要主要的是f数组的初始化问题， 要注意可以由题设得到一些东西可以作为 DP 开始的边界

  9. p1270 水题 完全背包模板题

  10. p1271 比较奇怪的一道题 其实这道题拿到以后我是有点蒙的， 感觉好像和 Dp 没有太大的关系，由于题中要求把集合中的数字分成两组， 他们两组的和是相等的。 所以我们自然可以想到先求一下前 n 项的总和， 判断是否能被二整除， 然后开始 DP， 这种 DP 是为了求方案数， 所以常规的求最优值的 max or min 函数就得换成求 sum 了，然后像一个0/1背包一样进行 DP 背包的容量为n项和的一半， 数字即是每一个物品， 每一个物品可以有放或者不妨入背包的选择， 最终f[s/2]中存的数值即为方案数的两倍， 因为一共算了两次。

  11. p1272 水题 完全背包模板题

  12. p1273 简单题 打了一个素数表， 然后进行完全背包就行了， 这个求得也是方案数， 注意边界条件的设置。

  13. p1286 区间DP 经典题 合并石子没有成环的情况， 枚举长度为阶段， 枚举左端点， 算出右端点， 在左右端点之间枚举分割点， 进行更新即可

  14. p1287 区间DP 比较简单的区间DP 注意题设中转移的要求即可。

  15. p1274 经典问题 多重背包 注意物品如果是有限个的话， 考虑两种情况， 如果物品个数与物品的体积之积超过了背包的大小， 那么直接按照完全背包来做， 如果没有的话， 考虑进行二进制拆分物品的个数：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int k=1, amount = a[i];
    			while(k < amount) {
    				for (int j=t;j>=k*w[i];--j) {
    					f[j] = max(f[j], f[j-k*w[i]] + k*v[i]);
    				}
    				amount -= k;
    				k+=k;
    			}
    			for (int j=t;j>=amount*w[i];--j) {
    				f[j] = max(f[j], f[j-amount*w[i]] + amount*v[i]);
    			}

    按照上面的代码可以把一个数量为a[ i ]的物品进行背包处理。

  16. p1276 二维费用的0/1背包问题 看清题，差不多就是一个板子，比常规0/1背包多了一个维度

  17. p1282 经典问题 多进程DP LCS 板子题

  18. p1285 简单题 由于有两口锅， 所以可以定义 f[i][j] 数组表示在 第一口锅 i 分钟时， 第二口锅 j 分钟时所能达到的最大价值， 枚举每一个 药 再分别枚举两口锅的时间， 判断如果结束的时间在枚举的时间之前的话， 进行转移， f[t][t] 储存的即为答案。

  19. p1284 经典问题 多进程Dp 阶段的设置也是设置一个数字 f[i][j] 表示 up 到第 i 个 down 到第 j 个的时候最大的匹配对数， 如果当前的 i 和 j 不相同的话， 向前寻找，如果可以形成匹配， 就进行转移，由于 f[][] 中储存的是匹配对的个数， 所以输出f[n][m]*2 表示为匹配的个数。

  20. p1296 经典问题 双进程问题， f[i][j][k][l] 表示第一个人到 i,j 第二个人到 k,l。 考虑状态的转移， 由于只会从两个方向转移， 理解即可， 注意DP问题有很多细节， 转移时的边界 或者 转移的判断都需要小心处理。

  21. p1290 经典问题 区间DP （并没有很看出来是一道区间DP）

  22. p1331 经典问题 二维DP 求最大正方形， 动态转移方程：

    1
    f[i][j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1 (c[i][j] != 1)