摸底考试 #3
T1 摆花
题解
诈骗题
取最小的 \(r_i-l_i+1\) 即可
时间复杂度 \(O(m)\)
T2 打饭
【数据范围】
\(n \leq 3 \times 10^5,k \leq \min(n-1,5 \times 10^3),-10^9 \leq a_i \leq 10^9\)
题解
线性DP好题
可以发现问题等价于将原序列分成 \(k\) 组,其中 \(n\%k\) 组中分别有 \(n/k+1\) 个数(第一类 )，别的 \(k-n%k\) 组分别有 \(n/k\) 个数(第二类)，即 \(j,k+j,2k+j…\left \lfloor n/k\right \rfloor \times k+j\)（或者 \((n/k-1)*k+j\)）
答案就是每个组中的最大值 \(-\) 最小值,而为了使差值最小,答案必须是连续的一段子序列,可以考虑DP
状态设计:设 \(dp_{i,j}\) 表示第一类的组已经分了 \(i\) 个,而第二类的组分了 \(j\) 个
状态转移:
记 \(n1=n\%k,n2=k-n\%k,l1=n/k+1,l2=n/k\)
则有两种转移:
-
\(dp_{i+1,j}=\min(dp_{i+1,j},dp_{i,j}+A_{(i+1)*l1+j*l2}-A_{i*l1+j*l2+1})[i<n1]\)
-
\(dp_{i,j+1}=\min(dp_{i,j+1},dp_{i,j}+A_{i*l1+(j+1)*l2}-A_{i*l1+j*l2+1})[j<n2]\)
答案即 \(dp_{n1,n2}\)
时间复杂度 \(O(\left \lfloor \frac{n}{k} \right \rfloor\times k)\)
T3 小象砍树
【数据范围】
\(n \leq 10^5\)
题解
树形DP好题