处理前缀和然后对所有前缀和 sumsumsum 模 ppp,于是原题的合并 [l,r][l,r][l,r] 使得最后剩下的元素可以被 ppp 整除,就等价为了判断 sum[l−1]sum[l-1]sum[l−1] 是否等于 sum[r]sum[r]sum[r]。
接着考虑 dp。
设 f[i]f[i]f[i] 表示序列 1∼i1\sim i1∼i 的答案为多少。
显然如果要合并第 iii 个元素的话那么直到合出符合条件的元素才停(不然没必要合)。
那么就有 f[i]=max(f[i−1],f[pre[i]]+1)f[i]=\max(f[i-1],f[pre[i]]+1)f[i]=max(f[i−1],f[pre[i]]+1)。
其中 pre[i]pre[i]pre[i] 表示与第 iii 个前缀和相等的前一个的前缀和的位置,当然如果没有 pre[i]pre[i]pre[i] 的话 f[i]=f[i−1]f[i]=f[i-1]f[i]=f[i−1] 即可。
使用您的 Hydro 通用账户