夏晓光(loveJY)的博客

zhx的DP

T1

n*n网格,每个格子有个数,有m个限制就是不能从权值为i的走到权值为j的

一条路径的权值是从起点到终点穿起来

然后起点任意问走k步能得到最大的数多少

$n,k<=100$

每个变化的限制就写入状态

$f_{i,j,k}$表示我现在走了i步走到j(j,k)的最大数是多少

转移考虑下一步,显然会发现我们从相邻最大的那个走过来

存的时候直接用字符串即可?

第一个问题是选出一些不相交的区间

显然可以$f_{i}$表示考虑了前i块地,然后i被种的最大收益

首先按照右端点排序即可

转移?考虑我们如果没有区间右端点的地一定不先考虑,然后我们枚举这个右端点处的区间是什么,设为[l,r]

$f_r=max(p_i+f_{1...l},f_r)$

树状数组或缀和优化

第二个问题我们可以先设计一个n^2状态

$f_{i,j}$表示考虑前i块地,然后已经开荒了i->j位置,j之前的不管

转移

$f_{i,j}=f_{i-1,j}-a_i+w$

$f_{i,i}=f_{i-1,0}-a_i+w$

$f_{i,0}=max f_{i-1,j}$

w是右端点在i的区间且左端点大于等于j的价值和

首先不难发现这个转移可以线段树优化?区间加?

zhx官方做法:

$f_i$表示最右种地区间编号为i,然后讨论之前区间和现在区间的关系

枚举一个r表示上一个被种的地盘

1. $r<l_i$

显然没有地被种过,直接开荒,和上个题一样

2. $l_i<=r<=r_i$

现在之前种的最靠右的在中间某个地方

f_{r_i}+=f_r+P_i+(sum_r_i-sum_{r-1})

都是一个区间最大值的查询,可以优化到log

3. $r>r_i$

会发现这个区间白给了

$f_{r}=f_{r}+p_i$

做完了,区间加

首先一定可以预处理别的位置对于中间四个位置我们放什么获得的代价

然后可以考虑中间之间的怎么搞定

九维dp

f_{i,j,k,l,m,n,o,p,q}$$表示考虑了前i个数,然后四个位置上放了j,k,l,m数,然后n,o,p,q为点四个数有没有这个i 转移的时候$O(2^4)$枚举即可  先有一个6维的背包dp $$f_{i,j,k,l,m,n}$$表示考虑选了i个...j个...k个...l个...有无队长,代价和为n的最大价值 考虑a+1个人选或不选,成不成为队长 然后这个能算出最优答案,但是不好计数,因为队长会自闭 我不当队长和当队长都自闭了 在加一维表示还有多少人能不能当队长?? 一定假了,复杂度上天而且还要再记一些 我们仔细思考这个东西挂掉因为当不当队长时的算重 所以我们可以发现钦定队长就能解决 把所有人排一下序,然后一个队伍中第11个人一定是队长了  显然要算贡献 然后考虑合并的时候怎么算新贡献 中间的边权会被算$n_i*n_j$ 然后$f_{i}$表示第i棵树的答案 但是你要直到某棵树内部走到某个点的路径权值之和 但是$g_{i,j}$表示i棵树内部所有点走到j的距离之和 答案就是$f[k]=f[i]+f[j]+n_i*n_j*c+g_{i,a}*n_j+g_{j,b}*n_i$ 这样可以求出第k棵树的答案 然后怎么求出g数组? $g_{i,j}$表示从第i棵树出发到j点距离? 首先右边内棵树上独自的贡献咋算啊,显然这个已经记录了 然后你会发现我们算另一棵树就要$$g_{c,d}$$(走到头上关键点) 然后+中间那条边的贡献,显然是$n_c*l$,每个点出发走到j 然后我们再考虑这个从某个关键点到另一个关键点的距离?$h_{a,b,j}*n_c$ h怎么更新?如果在一棵树直接更新,在两棵树就从一颗加上关键点+l来转移 然后这个关键点的大小?映射..... 显然我们写记忆化搜索就不需要映射了? 直径?显然我们有点集直径合并的性质Qwq,关键点就只剩下几个了  $f_{i,j}$表示点i为根的子树里面有j只鹰,然后这个东西可以想象转移 1. j-1飞走 f_{i,j}=f_{i,j-1}*一个系数 显然... 2. j飞进去 会发现,我们要决定飞入那个子树.... 然后我们不知道没课子树有多少鹰 $n_1+n_2+....n_k==sth$ $g_{i,j,k}$表示考虑了前i课子树已经飞入l只鹰,k是0/1变量,表示我们第j只鹰定没定 每次dp一个儿子的时候考虑这个儿子飞进去多少,然后是否飞进去 如果不飞过去,我们直接背包求和 如果飞进去我们还要乘$f_{v,n_v+1}$ 插板法/se orzljh 先枚举那个儿子飞入,然后枚举第j只鹰停留时多少个儿子 $$f_{i,j}=\sum_{r=1}^k 1/k \sum_{n_r=0}^{j-2} f_{p_r,n_r+1}

还不够,我们里面还有一个方案数,也就是说实际上概率不是这个

$f_{i,j}=\sum_{r=1}^k 1/k \sum_{n_r=0}^{j-2} f_{p_r,n_r+1} *\binom{nr}{j-2}{\frac 1 k}^n_r\frac{k-1}{k}^{i-2-n_r}$

之前背包的式子也要写概率QAQ

TC Open 2014 Round 1B P3

老师太懒没写

显然状压不太行

优化状压?你会发现我们不需要太多信息

只需要知道是否是某个数的倍数

$f_{i,j}$表示我们选了i个数,gcd为j的先手是否必胜

转移考虑

1. 选择j的倍数

看看有多少数是j的倍数c,然后如果$i<c$

我们可以再选一个j的倍数,gcd不变

2. 不选择j的倍数

那之前一定没有选择过他

转移到$f[i+1][gcd(j,a_k)]$

然后博弈论DP就解决了

orzwyz

n个点,深度为k的二叉树有多少种

考虑转移?枚举右子树多少点,然后深度是什么

先钦定左子树达到$j-1$

$f_{i,j}=\sum_{k=1}^{k-1}f_{k,j-1}\sum_{d=0}^{i-1}f_{i-1-k,d}$

然后我们还要加上右子树成为$j-1$啊/ll

$+\sum_{d=0}^{j-1}f[k][d] f_{i-1-k,j-1}$

可以前缀和优化$O(n^3)$

此时你会发现我们可以优化状态,直接dp前缀和

$f_{i,j}$表示点i深度小于等于j的方案数

然后转移$$\sum_{k=0}^{i-1}f_{k,j-1}*f_{i-1-k,j-1}$$

finished