动态规划
1.DP方式
自己更新别人or别人更新自己
2.几种DP
区间DP
数位DP
状压DP
插头DP
树形DP
其他DP
3.例题
-
【区间DP】n个矩阵，第i个矩形大小为n[i-1]n[i]，求矩乘顺序使得运算次数最少 nm，mk->nmk
- 状态 f[l][r]：把第l个矩阵到第r个矩阵的矩乘做完所需要的最小代价
-
f[l][l]=0 f[l][r]=min(f[l][k]+f[k+1][r]+n[l-1]*n[k]*n[r])|l<k<r ans=f[1][n] - 一般做法，枚举区间、断点，n^3.
-
坑点
若l从小到大枚举，f[l][r]由f[k+1][r]转移，但f[k+1][r]未被更新；then，枚举区间长度，保证转移的正确性。
-
【树形DP】dis(i,j):i到j距离，求两两点对的距离之和
- i是1的儿子 f[i]到子树内所有点距离 g[i]到非子树内点的距离
- 在子树里：
f[i]=Σ(j∈son[i])(f[j]+sz[j]) - 不在子树里：
g[i]=f[1]-(f[i]+sz[i])+sz[1]-sz[i]
- 在子树里：
- 一般形态：f[i]->以i为根的子树的信息（一般从叶子节点向上dp）
- i是1的儿子 f[i]到子树内所有点距离 g[i]到非子树内点的距离
- 【数位DP】给定两个数l，r
- 填数：
f[i][j][k] 从高位向低位填，已经填到第i位，j、k 0/1 变量 是否满足给出的条件（大于等于左边界，小于等于右边界） - 转移：枚举下一位填什么数
- 降维：（3 to 2）只关心上界，ans取[1,r]-[1,l-1]（前缀和思想）
- 入门题：windy数
- 填数：
- 【状压DP】TSP（旅行商问题）n个点，给出坐标，从一号店出发，把所有点走一遍的最小距离之和为多少
状态：f[s] 走过这些点需要的最小距离转移： 走到if[s] -> f[s|(1<<i)] 没法转移？加一维！-
- 转移：
f[s][j] -> f[s|(1<<i)][i]+dist(i,j) - P1171 售货员的难题
- 论文：基于连通性状态压缩的动态规划
- 【插头DP】NOIP 不考 （hdu eat the tree ）
4.神仙 其它DP
- 【数字三角形2】原题目条件下，%m最大
-
- 有n个数字，选出一个子集的数字之和是m的倍数（n<=1e4,m<=100）
-
-
玩游戏，三种操作,当
x+y>n 时，只能1操作，如果y>=n 输-
-
1.(x,y) -> (1,x+y) -
2.(x,y) -> (2x,y) -
3.(x,y) -> (3x,y)
-
-
-
所有非2的倍数、3的倍数的x均不可能(
x=2^a*3^b ) -
状态:
f[a][b][j] -
P3541
-
-
【数位DP】给出三个数l,r,k满足[l,r]内各位数乘积为k的数有多少个
-
- 优化！入手角度：t->一定为个位数乘起来
质因子：2，3，5，7
∴t=2^a*3^b*5^c*7^d -
-
* 但是....还是会炸（被卡常） * 首先DFS出只有2，3，5，7四个质因子的所有数。 * dp可降维 * bzoj2757 -