dp总结
2019-08-17 本文已影响0人
saploser
P1216 [IOI1994][USACO1.5]数字三角形 Number Triangles
- 第一次tle了，然后发现自己犯了一个很傻的错误，想用数组递归，可每次还是重算了，于是有加了一些，就AC了
记录详情 - 入手点：发现题目问的是最值，于是想到贪心和dp（若暴力搜索的，感觉基础算法是O（n！）），感觉没有直接贪心的思路，且dp好像比较好写（数据不是特别大），于是使用dp
P1115 最大子段和
- 错了一个点，感觉是因为要找非空子段（若所有数全是负数，则输出应该 < 0，而我的解法的输出是0），可没想好如何用动态规划解决
记录详情
最长上升子序列
- O(n^2)用dp很好写可过不了，优化要用dirworth定理证明（或找规律），不会
dp博客（找到后删掉此条）
P1464 Function
- 直接记忆化搜索即可
- 记录详情
P1255 数楼梯
- 用数组递归（因为比较稠密），n <= 5000 ，必须用高精度
- 开始时用struct时没写构造函数，于是没过，可记得有老师说不写构造函数会自动清空
- 记录详情
-
总结（待补充）
P1002 过河卒
- dp计数，若被马踩，直接return0，若超出棋盘，return0，若到达，return1，否则dp
- long long
- 记录详情
P1049 装箱问题
- 这道题老师讲转移方程是dp[i][j] = dp[i - 1][j] || dp[i - 1][j - w[i]] （可用滚动数组省略i）可感觉只能解决是否能完美放下的问题
P1541 乌龟棋
- 这道题直接用dp（a，b，c，d）表示有a个1，b个2，c个3，d个4，直接dp即
- 老师又说可以用map做记忆化，没想明白
P1048 采药
- 这道题感觉直接dp即可，样例和手动生成的都过了，可最后只ac了2个点
- 记录详情
P1164 小A点菜
P1507 NASA的食物计划
这题第一次样例过了，但是提交只得了10分，检查后发现有个错误；想问一下老师，如何自己出测试数据
yl教练继续：
P1060 开心的金明
01背包
P1064 金明的预算方案
变种01背包
image.png
image.png
image.png
SP39 PIGBANK - Piggy-Bank
完全背包
image.png
image.png
image.png
image.png
image.png
自学【多重背包】和【混合背包】
image.png
P1466 集合 Subset Sums
01背包计数
P1474 货币系统 Money Systems
完全背包计数
P2733 家的范围
矩形DP
image.png
image.png
P1006 传纸条
矩形DP
image.png
P1387 最大正方形
矩形DP
image.png
