动态规划
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 -