中等水平各类dp解题报告
- 前言
最近退化了，做题养生
考虑 \(f_i\) 表示序列 \(a_{1 \cdots i}\) 的最长子序列长度，以 \(i\) 结尾。
转移就是 \(f_i = \max_{j=1}^{i-1} f_j + 1\), 要求 \(a_i \& a_j \neq 0\)
时间复杂度 \(O(n^2)\)
优化肯定在于 \(a_i \& a_j \neq 0\) 这个条件
考虑 \(a_i\) 的每一个为 \(1\) 的二进制位 \(k\), 只要 \(a_j\) 第 \(k\) 位也为 \(1\) 即可。
\(g_i\) 维护每一位为 \(1\) 的最大\(f_i\) 辅助转移即可。
时间复杂度 \(O(n\log A)\)
背包模型。预处理第 \(i\) 场投入 \(j\) 人的收获总分 \(w_{i,j}\)，套上一个分组背包即可。
时间复杂度 \(O(ns(m+\log s))\)
题意：找出最长严格单峰子序列。
考虑保存前缀最长严格递增子序列与后缀最长严格递减子序列的长度，枚举中间那个峰统计答案即可。
时间复杂度 \(O(n\log n)\)
没法提交代码，放这里
#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define db double
#define mod 998244353
#define N 10005
int n,cnt,a[N],b[N],f[N],g[N];
int main(){
while(scanf("%d",&n)!=EOF){
fr(i,1,n)scanf("%d",&a[i]);
cnt=0;
fr(i,1,n){
if(a[i]>b[cnt])b[f[i]=++cnt]=a[i];
else b[f[i]=lower_bound(b+1,b+cnt+1,a[i])-b]=a[i];
}
cnt=0;
for(int i=n;i;i--){
if(a[i]>b[cnt])b[g[i]=++cnt]=a[i];
else b[g[i]=lower_bound(b+1,b+cnt+1,a[i])-b]=a[i];
}
// fr(i,1,n)printf("%d ",g[i]);puts("");
int ans=0;
fr(i,1,n)ans=max(ans,(min(f[i],g[i])<<1)-1);
printf("%d\n",ans);
}
return 0;
}
求解比较难，但是我们发现天最多 \(O(Dm)\)，考虑通过二分转化为判定。
如果以 \(T\) 天为DDL，考虑 \(f_{i,j}\) 表示前 \(1\) 到 \(i\) 个人第一个软件在 \(T\) 天内做了 \(j\) 个模块，那么能在 \(T\) 天内第二个软件最多做的模块数量。
这个明显是背包，转移：
\[f_{i,j} = \max f_{i-1,j-k}+(T-kd_1)/d2 \]时间复杂度 \(O(nm^2\log Dm)\)
应该容易优化掉转移的枚举变成 \(O(nm\log Dm)\)
断环成链的区间DP模板。
\(O(n^3)\)
记买到 \(i\) 种名字后还要期望要买 \(f_i\) 瓶才能集齐。有：
\[f_n = 0 \\ f_i = 1 + \dfrac in f_i +\dfrac {n-i}n f_{i+1} \]这是因为集齐 \(i\) 个后再买一个，有 \(\dfrac in\) 的概率买到重复的，有 \(\dfrac {n-i}n\) 的概率买到新的。
解得:
\[answer = f_0 = \sum_{i=1}^n n/i \]然后就是高精度模板。
关键解决去重，由于只能向右向下移动，我们同时维护两条路径，记 \(f_{x,y,z,w}\) 表示第一条路径走到 \((x,y)\)，第二条走到 \((z,w)\) 的最大得分。枚举两个走的方向转移，注意如果走到了同一个点只能取一次。
时间复杂度\(O(n^4)\)
观察到只有 \(x+y=z+w\) 的点有意义，转而维护 \(f_{x+y,x,z}\)
时间复杂度\(O(n^3)\)
简单分析后发现覆盖操作之间相互包含或相离，反正不会是相交(肯定亏了)。
于是考虑区间DP，\(f_{l,r,c}\) 表示当前 \([l,r]\) 区间都为颜色 \(c\)，还需要染色的最小次数。
若 \(a_l=c\)，\(f_{l,r,c} = f_{l+1,r,c}\)
否则 \(f_{l,r,c} = 1+\min_{p=l}^r f_{l+1,p,a_l}+f_{p+1,r,c}\)
时间复杂度\(O(n^3C)\)
从第三部分开始，前面太水了。。
区间DP。若只记 \(f_{l,r}\) 可能有一些拼接区间的操作无法顾及到。
考虑到拼接可以认为是一个个接上去的，记 \(f_{l,r,k}\) 表示删掉 \([l,r]\) 及 \(k\) 个额外 \(s_r\) 的最大得分。
转移只有: 直接删掉 \(s_r\) 及后面的东西，或者枚举一个 \(p\) ，\(s_p=s_r\)，删掉 \([p+1,r-1]\) 从而拼接 \(s_r\)。
时间复杂度\(O(n^4)\)
矩阵快速幂模板，点太多离散化即可。
\(O(T^3\log n)\)
HH是变化之神。
关键是处理“不会立刻沿着刚刚走来的路走回”的限制。
使用点边互换技巧。等价于找到边的长为 \(T\) 的序列使第一条边起点为 \(S\)，最后一条边终点为 \(E\)，任一条边终点为下一条边起点。构建边链接关系的有向图，一条边终点为另一条边起点就给它们连边，但是一条边不能连接其反边。
矩阵快速幂，与上题的 \((\max,+)\) 矩阵不同，这题是 \((+,*)\) 矩阵。
\(O(m^3\log t)\)
\(f_{u,(0/1)*6}\) 表示处理了以 \(u\) 为根的子树，\(u\) 有没有消防局，\(u\) 有没有被消防局覆盖，\(u\) 的儿子有没有存在消防局，\(u\) 的儿子有没有全被消防局覆盖，\(u\) 的孙子有没有存在消防局，\(u\) 的孙子有没有全被消防局覆盖，这种情况下的最小消防局数，转移即可。
\(O(n)\)，但是有 \(2^{12}\) 的巨大常数，其实可以优化
下落等价于人向上走，考虑普通的DP就是 \(f_{i,j,k}\) 表示当前在 \((i,j)\) 上拥有 \(k\) 个左括号，最多有几个括号对已经确定。转移枚举方向，简单做到 \(O(n^3)\)，还原方案记录决策点即可。
问题在于选出字典序最小的方案，直接用一个$ \leq 2^{300}$ 的大数来存储并比较当前的字典序即可。时间复杂度 \(O(\dfrac{n^4}w)\)，不需要记录决策点，滚动优化空间，空间复杂度 \(O(\dfrac{n^3}w)\)。
代码还没写
不在题单里，但我刷到觉得比较精彩。
发现一条边断掉后它对应的子树就废了，所以不如断掉它同时断掉子树内的所有边，于是问题转化为每个果实选择收获或者不收获，但是收获时间自下往上必须单调不减，问总共最大价值。
DP，\(f_{u,i}\) 表示 \(u\) 子树内选择的收获时间不超过 \(i\)，子树内总共最大价值。
合并 \(u\) 和 \(v\) 就是：
\[f_{u,i} \leftarrow f_{u,i} + f_{v,i} \]最后考虑 \(u\) 可能要选：
\[f_{u,j} \leftarrow \max (f_{u,j} , f_{u,d_u}+w_u) \]直接来时空 \(O(n^2)\)，34pts
看前面那条转移容易想到线段树合并。处理后面那条转移需要标记永久化，合并时标记也相加。比较麻烦，可以看题解。
时空 \(O(n\log n)\)
标签：cnt,log,dfrac,复杂度,中等水平,转移,解题,消防局,dp From： https://www.cnblogs.com/zsj6315/p/18521268