Day 10 2020.3.10
动态规划（五）
作业
1.P4170 [CQOI2007]涂色
2.P1837 单人纸牌
【题面】
题解
如果看过洛谷题解就是开个f[]^9九维数组记 录每堆牌还剩下多少的时候想拿空的概率。 我看谁不珍惜自己的手
这题就是一个用五进制很好的实例，事实证明代码阅读性下降了但码量明显缩短了。
3.P1140 相似基因
给两段基因，允许你插入任意的-使得它们 一样长，然后进行匹配，匹配的收益已给 出，问收益最大多少（-不可与-匹配）
题解
很套路了对吧，大家是不是已经熟练了呢？
dp[i][j]为a串1ib串1j匹配的最大收益。 有三种情况：(a_i,b_j)互相匹配，a[i]与-匹配， b[j]与-匹配。取最大值即可。
转移即可。
4.JSK43368
https://nanti.jisuanke.com/t/43368
给(nle 20)个坐标，每个坐标有只宝可梦，你在((0,0))，问你最少走多远可以集齐全部类型的宝可梦（你走路只能按照曼哈顿距离走）
题解
宝可梦最多20种，记录f[i][j]表示我到i点已 经拿到宝可梦的状态为j，那么O(n2*2n) 枚举转移即可。
例题
1.P1002 过河卒
题解
热身一下，f[i][j]为走到(i,j)的路径条数。
显然f[i][j]=f[i-1][j]+f[i][j-1] • 那么对于马支配的坐标的f值就要固定为0了。
2.P1941 飞扬的小鸟
题解
dp[i][j]表示第i列在j的高度想要通关的最少点击次数。不难发现点击的时候因为天花板死不掉所以可以点无数次——相当于完全背包。不点击选择下降的时候只能下降一次—— 相当于0/1背包
剩余的方程是不是就好列了呢？
首先对于所有状态初始化INF，然后对所有管道所在位置初始化INF，每次飞过一个管道的时候看看是否存在情况飞过管道了，如果没有输出当前位置。
全飞出去之后统计最小值。
3.P5662 纪念品
题解
不难证明只要卖的时候比买的时候价格贵就可以卖：如果未来有更贵的时候那我当 天卖完当天再买回来就好了。
换句话说我们只关心两天之间纪念币的差值，负就亏了（显然我们不会让自己亏） 正就赚了。
那么显然每天都赚尽可能多的钱就是最优解。
因此对于第i天进行完全背包，物品价值为 第i+1天价值-第i天价值，体积为第i天价值。 每天结束后更新钱量为原有钱量+今天最多 挣了多少钱。 复杂度(O(nt imes 10^4))
4.P1049 装箱问题
题解
题目要求求出最小的剩余空间，也就是要 求出最大的可装重量
这不就是背包了？
5.P2607 [ZJOI2008]骑士
每个人有一个价值和一个最恨的人，现在组出一个队伍使得价值最大且没有仇恨关系(N ≤ 1 000 000)
题解
如果我们把被仇恨的人向仇恨他的人连一条有向边的话，那么我们不难发现，我们 得到的图将会是若干个基环外向树（就是一个环，环上每个点都挂着一棵树）。 如果没有环，只有树的话，那么显然就是 “没有上司的舞会”的那道题。
那么基本思路就没有变，f[i][0]表示i不选的时候的最大价值，f[i][1]表示i选的时候的最 大价值。
我们显然可以先枚举树在环上的根，然后将环拆开成树，对这棵树进行一遍树形dp。
但是显然拆开部分(v,rt)也需要考虑，不难发现f[rt][0]是对的但是f[rt][1]有可能错误， 错误在于v一定不能取，可是这个状态却没有这个表示。所以我们令f[v][1]=f[v][0](就是 v一定不取啦)重新更新环上的点即可。