DP专题

hdu 2955 转换一下下标，求不被抓概率最大值，常用转换技巧 hdu 4281 MTSP问题，对于TSP问题状压即可，MTSP对TSP做背包（这复杂度好唬人啊 小技巧 枚举i的子集 for(int j = (i-1)&i; j; j = (j-1)&i) Zoj 3524 Crazy Shopping 拓扑排序加完全背包，注意能更新的点，核心是按拓扑序先对 当前点跑完全背包，再对其所能到达点更新能量 Zoj 3662 Math Magic 题意给定N,M,K选k个数满足sum(a1,a2...ak) = N, lcm(a1,a2..ak) = M 的方案数，N，M <= 1000, K <= 100 ，求M的因子，dp[i][j][k]表示选i个数sum为j，lcm为k 的方案数，i可滚动数组优化 Tips：k个数的lcm一定要是M的因子(非M因子一定不满足条件)因此可以枚举因子，而不枚举M 滚动数组时要把先把当前维的值清空在转移 [代码](https://www.luogu.com.cn/blog/littlechai/zoj-3662-math-magic)