作者自己的学习笔记,因此会不断更新
UPD:T1-T13 7.25 9:58
博客食用更佳
https://www.cnblogs.com/czyty114/p/14987595.html
BZOJ 3864
https://darkbzoj.tk/problem/3864
我们的任务是统计合法T串的数量
发现|S|很小,猜到是状压,但不知道如何设计状态,如果只是用S表示与哪些位置匹配了似乎也很奇怪,不大可做
如果设fi,j,m为S[1..i]和T[1..j]的LCS为m的方案数,再按LCS去转移。
但这样会导致算重,因为同一个T[1..j−1]有可能既属于fi,j−1,m又属于fi−1,j−1,m−1
所以划分有问题的时候,考虑多加几个条件。
想个最狠的,假如我们很nb,把LCS(1,j-1),LCS(2,j-1),…,LCS(i,j-1)都记录下来记为S,那么同一个T[1..j−1]就只可能属于一个S中了。
但肯定开不下来,发现LCS(i,j)和LCS(i-1,j)最多差1,于是就可以用二进制S表示差分数据去转移
正睿提高组十连测day7-C 种树
有n个人,我们要把他们分成若干个队伍,第i个人所分到的队伍的人数数量≤ai
两种方案不同当且仅当存在原先在同一个队伍两个人被分到了不同的队伍
n,ai≤2000
我们发现,对于同一组的人来说,限制的瓶颈在于ai最小的那个人,设其为x
那么对于一个队伍来说,我们只需在选x的时候,一块选上即可
我们首先考虑将ai从大到小排序,枚举i的时候,我们只关心前面还没选的人的数量
设dpi,j表示前i个人,目前有j个人还没选的方案数
dpi,j=i∑k=0dpi−1,j+k−1×C(j+k−1,k−1)
直接转移是n3
优化,把按人dp换成按队伍dp来做
设dpi,j表示组好了队伍数≥i,剩下j个人的方案数
dp_{i-1,j+b_{i-1}-k(i-1)} <– dp_{i,j}\times C(j+b_{i-1},k(i-1))\times \frac{k(i-1)!}{{(i-1)!}^k\times k!}
发现转移过程有调和级数,复杂度就是O(n^2 log n)
BZOJ 3594
\;
操作只能是一个后缀,然后把每个数的增量一定就是这种形式:000111222333555
我们要同时满足i<j,a_i+d_i\leq a_j+d_j, l_i < l_j,且是一个二维的前缀。
所以我们不能一层一层的去清空。
那么就维护一个二维的树状数组
四边形不等式
\;
对于这类dp:
f_j=min\{f_i+w(i,j)\}
\;
如果满足w(i,j)+w(i+1,j+1)\leq w(i,j+1)+w(i+1,j)
那么决策一定是满足单调性的
大概就是:将上面的柿子移项,发现对于决策i,j变到j+1的过程中i的增量较大一些
所以在j不断移动的时候,i就可能不是最优决策了,且决策点一定会往后走
用单调队列做可以做到O(nlogn)
且注意四边形不等式不能做最大值
\;
对于2D1D问题,即:
f_{l,r}=min\{f_{l,k}+f_{k+1,r}+w(l,r)\}
\;
如果w函数满足区间包含单调性且满足四边形不等式,那么f也满足四边形不等式
证明我不会啊,估计就咕了吧
而如果f_{i,j}是满足四边形不等式的,最优决策点best_{i,j}是单调的,即:best_{i-1,j}\leq best_{i,j}\leq best_{i,j+1}
时间复杂度可以看成一个矩阵上的图来分析,共有n条对角线,每条跨越的幅度为n,所以能优化成n^2
f_{i,j}=min\{f_{k,j-1}+w(k,i)\}
\;
也是同样的道理
luogu P3648 序列分割
\;
观察到最终的答案和分割的顺序没有关系,一个数只不会和与它在一组的数产生贡献
于是考虑从后往前分割
如果用求没有贡献的和最小的那个dp,w是满足四边形不等式的,但是那样还带一个log,过不去
考虑新的做法
即换一种dp形式:
dp_{i,j}=max\{dp_{k,j-1}+(s_i-s_j)\times s_j\}
\;
这个东西虽然不能用四边形不等式来做,可以考虑去斜率优化,把j先去掉,因为是相邻的两维嘛
dp_{i}=max\{dp_{j}+(s_i-s_j)\times s_j\}
\;
要是dp_j+(s_i-s_j)\times s_j最大
不妨设其为c,s_j=x,dp_j-s_j^2=y
s_ix +y=c
y=-s_ix+c
维护一个上凸壳就可以了
BZOJ 2131 免费馅饼
\;
一开始的想法是按t排序,是为了保证选的顺序一定是从左到右
然后推出:2t_i-p_i\geq 2t_j-p_j (p_j\leq p_i)
或2t_i+p_i\geq 2t_j+p_j (p_i\leq p_j)
然后我把这个东西成了一个二维前缀矩阵最大值问题。
发现二维树状数组内存开不下,而有两维,有因t已排序好了,无法去处理
考虑原始柿子:
2(t_i-t_j)\geq |p_i-p_j|
\;
这个绝对值非常的讨厌,但可以发现,只有上面两个柿子都满足条件才可以。(因为一交换变成负的更满足条件了)
这样就不用去讨论绝对值里面正负的问题。
从而得出:i在j后面选,当且仅当:
2t_i-p_i\geq 2t_j-p_j
且
2t_i+p_i\geq 2t_j+p_j
按一维排序,另一位树状数组维护即可
总结:推出两个东西前后选,必须满足什么条件,排序就能消去一维,有些绝对值符号,看看一种情况能否包含另一种(即满足这一种就一定满足那一种),就可以去掉了
放置街灯
\;
n^2做法直接树形背包解决
考虑线性做法
因为题目同时给了两个条件,要在第一个条件最小化的情况下,最大化第二个条件。
不妨对第二个条件做个补集转化。
现在相当要让两个条件整体最小化,但第一个条件的优先级更高。
不妨选进制k>n,那么把选法压缩成一个k进制数就可以了。
luogu P5504 柠檬
\;
考虑只能从颜色相同的位置转移,且一定会选这种颜色。
否则一定可以将区间两段同时缩进,得到一种不劣的方案。
发现,这玩意是满足四边形不等式的,因为平方,i越小,增长的速度越快。
按理说,这东西的决策点应该是单调递减的。
但有可能新加入的决策非常的优,导致决策点又往右横跳。
维护一个单调栈存储决策点的信息,每次x入栈时看栈顶被次顶干掉的时间如果比栈顶干掉x的时间早,栈顶肯定就没用了。
然后转移i时,要时刻注意栈顶是否已经是不优了
CF1509C
\;
从前往后扫的过程中,只会关心当前最小值和最大值,看作是两个指针,它们一定会不断的往下和上扩展,导致极差变大。
那我们肯定是让它往上或往下扩一个值。
所以考虑区间dp
dp_{l,r}=min(dp_{l+1,r},dp_{l,r-1})+s_r-s_l
\;
s要提前排序,复杂度:O(n^2)
CF441E
\;
直接去求最小距离不大现实,最多做到n^2
显然可以二分,变成判定问题。
接第i个订单的人肯定要停留在x_i,所以只需记另外一个人的位置,记为j
那么设dp_{i,j}表示接了前i个订单,另一个人停在了j的位置是否可行
转移:看是哪个人接了i+1订单,->dp_{i+1,j}或dp_{i+1,i}
显然对于|x_{i+1}-x_j|>mid,显然这样的j挂掉了,而发现,如果按坐标排序,这相当于弹出首尾两段的一些状态。
而如果|x_{i+1}-x_i|\leq mid,就要加入x_i这个状态。
所以我们需要维护一个有序序列,支持删除和插入,set是最好的选择
O(nlogn\times log w) w为值域
CF1096E
\;
显然,我们会先去枚举1的分数,然后再枚举有多少人和他同分。
剩下的问题就是有i个人,分数和为s,分数都不超过m的方案数
对于这种分数都不超过某个值,很难去搞,如果只是简单的枚举,复杂度又太高。
不妨我们去容斥,看有多少个人超过了这个值。
那么先塞给这些人m+1的分数再说,然后剩余的分数随便分配就好了
AGC016F
\;
博弈论dp
对于多个有向图博弈问题
sg(s)=sg(s_1)\;xor\;sg(s_2)\;xor… xor\;sg(s_m)
现在要让先手必胜,即sg(s)>0,所以sg(1)\neq sg(2)
将其分层,一一确定每个点的sg值
我们按照从小到大的顺序,枚举S的子集T,对于x\in T,令sg(x)=0
那么剩余的部分G,G中的每一个点,都要向T中连至少一条边,反过来是随便连。
那么不断分层分层,在dp的过程中保证1和2在同一层即可
ICPC2018 Gem Island
\;
考虑总方案数是n(n+1)..(n+d-1)
对于每一种分配方案,我们想知道他的方案数有多少
首先勒令分裂的宝石的主人是谁,在这个基础上方案数已有\frac{d!}{\prod a_i}
但注意到这里我们只关心哪天晚上分裂的主人是谁,而并没有关心是哪一颗宝石
所以发现对于同一个人,后面宝石数会不断增加,还要乘上个a_i !,那么就消去了
所以方案数一定是d!
\;
经典dp方式
\;
搭楼梯
在考虑贡献的时候,正常思维应该是竖向考虑,考虑前r的和
不妨去横向考虑,对于每个x,设b_x为a_i\geq x 的数量
那么x的贡献是min(b_x,r)
在dp的时候,我们也要这么横向考虑
因为知道\sum_{i=1}^n a_i=d
设f_{i,j}表示前i的高度,已经搭了j个格子的方案数。
转移时,看一下最高层搭了多少个格子
显然这里a_i并不是严格不增的(只不过我们考虑的时候这样方便一些)
而且这样我们也能很方便的知道,此时a_i\geq x有多少个了