#动规个人总结三-DP-动态规划

· · 个人记录

方案数的平方？

也就是两个结果相同的方案两两组合的方案数，我们往往可以把这个过程复制一遍，存在状态里，同时进行这两个过程，保证中途的结果相同。

例题：管道取珠

观察到a[i]^2就是取出它的方案的两两组合，所以我们多设一维DP：f(i1,j1,i2,j2)表示第一组管道的还剩(i1,j1)，第二组管道还剩(i2,j2)，取出来的情况相同，的方案数，观察到i1+j1=i2+j2，所以可以少计一维。

2018-2019 AECF-I

Bitset优化完全背包

DP的关键在于枚举

DP的重点是发现最优子结构

[ZJOI2013]蚂蚁寻路。我们直接DP不好做。但我们可以反过来看，发现是高低相间的矩形，这样我们就可以DP了。这道题需要注意一些细节，比如步步和0取max（因为可以从任意位置开始），但是取max的时机需要注意。

从多个角度发现最优子结构。

如果DP减法（不取...）不好DP，可以DP加法（取...）。

树形DP优化方向

如果DP和子树的关系不大和祖先的关系较大，可以尝试将树上DP换成序列DP（dfs序或bfs序），变成dp[i][...]表示前i个...，这样可以省去合并子树的过程，使得每个点的转移方向只有一个。

CF1111E Tree

不要被区间DP禁锢住！！！

有些看似很像区间DP的题，尝试在序列上1-n顺序DP能否做。

决策单调性并不代表代价函数是凸的或者递增的，不能三分（但是可以骗分），只能用专属算法：分治/决策队列。

知道有根树的数量，如何求无根树的数量。我们可以对一棵树强制以重心为根。但是要减去重心有两个的情况（注意，这时候选择的两棵树不能重复，因为重复的树之前只被算了一遍）。

分成k块，求每块大小的乘积，可以转化为求从每块中选一个点的方案数

看到一类带有概率的最优化问题（比如让你给每个点分配一个贡献系数），转化为最优子结构+DP。

斜率优化新技巧

如果插入横坐标不单调，可以：

1.二进制分组。sort一遍求凸包

2.李超线段树维护上半平面交

背包的应用

求\sum a_ix_i=w的解数，可以用背包！

有时候，DP的转移方程可以忽略一些部分

[USACO19JAN]Redistricting

考虑转移方程：

dp[i]=dp[j]+(sum[i]-sum[j]\le 0)

注意到如果dp[x]<dp[y]，那么无论后一项是怎样的，用x更新肯定没错。如果dp[x]=dp[y]，我们肯定用sum最小的更新。

两维斜率优化？

遇到形如f[i]=\max_j(x_ia_j+y_ib_j)，看上去好像不能做？处理非常Trick：把y_i除过去！

区间DP

遇到贡献与若干区间有关的问题，难以处理区间相交的决策，尝试区间DP，只考虑被[l,r]完全包含的区间的贡献。

跨度为2的约瑟夫问题

设环长是i，i的二进制有b位，那么最后活的人是i在宽度为b位的情况下循环左移一位的结果。

树形背包注意转移顺序！！！遇到使用临时数组的情况，要先把儿子DP完！

优化转移时，一种思路是看谁能贡献给它，还有一种思路是他能贡献给谁

有时候往往后者更简单一些（eg.斜率优化...），因为你是从已知出发。

一些优化dp转移的方法

DP要敢于设状态，从暴力DP开始优化！