\(\text{Problem - 889E - Codeforces}\) \(\text{*3000}\)
题意
给一个序列,对于一个非负整数 \(x\),有一个式子:
\[x\bmod a_1+x\bmod a_1\bmod a_2+...+x\bmod a_1\bmod a_2...\bmod a_n \]求出上式的最大值。
思路
先去寻找题目的性质。
首先 \(x\) 的值单调不增,然后如果当前 \(x\) 的值小于 \(a_i\) 则对 \(x\) 无影响。
对于上述两条,我们首先能够总结出一点:一定存在一个答案区间 \([l,r]\),其中 \(ans_l=ans_r=a_l-1\)。说人话就是首先答案是一段一段的递减区间,然后一定有一段区间的值顶着对应区间的上界。因为如果没有,则可以至少令当前 \(x+1\),然后答案更大。然后就是 \(x+1\) 的操作的正确性是因为余数性质:\(x+y\equiv x\%p+y\%p\pmod p\),所以只要操作后 \(x\) 小于 \(p\) 后面区间就不会变成零,并且我如果将最初的 \(x+1\),那么所有位置的 \(x\) 就都会加一,答案也都会加一。
然后对于这道题有一个显然的暴力 \(dp\)。我们令 \(f_{i,j}\) 表示计算到位置 \(i\) 当前 \(x\) 值为 \(j\) 的最大值,转移显然,复杂度是 \(O(n\times a_1)\)。
考虑能否优化状态。因为答案区间是一段一段的递减,其实我们枚举 \(j\) 的时候就会发现最下面的答案是 \(i\times j\),然后上面变成一段更小的单调不增的区间。然后根据之前发现每个位置对应的 \(x\) 同加同减,也就是说他们的相对值不变,所以如果我们不去维护最后的答案而是只维护上层的答案,那么更新(转移)上面的答案就是 \(O(1)\) 的。比如我转移状态需要修改 \(x\) 时,我只需要把区间整体答案修改即可。
所以我们得到了最终的 \(dp\),设 \(f_{i,j}\) 表示计算到位置 \(i\) 当前 \(x\) 值为 \(j\) 时每个 \(x\) 大于 \(j\) 的部分的和,最后答案就是 \(\max_{0\le i<a_n} \{f_{n,i}+n\times i\}\)。转移时对于 \(f_{i,j}\) 分成两种情况考虑:
- 直接转移到 \(f_{i+1,j\%a_{i+1}}\):这时 \(j\) 变小,答案加上 \(j-j\%a_{i+1}\) 的高度;
- 每次新维护一个 \(f_{i+1,a_{i+1}-1}\):答案加上的高度类比第一种即可。
存在第二种转移是因为性质一告诉我们一定会有一个 \(x=a_i-1\),所以每次需要维护。
关于复杂度的话,考虑对于每个 \(i\),至多存在 \(0,1,2...,a_i-1\) 一共 \(a_i\) 种状态,所以初始状态可看成 \(n\) 种;每次转移会将 \(j\) 转移到 \(j\% a_i\) 上,已知取模复杂度是一只 \(\log\) 所以状态是 \(n\log x\) 的。然后实际 \(dp\) 的时候,第一维滚掉,第二维发现 \(j\) 太大用 \(\text{map}\) 存,然后 \(\text{map}\) 也有一只 \(\log\),所以时间复杂度是 \(O(n\log x\log n)\)。
代码
signed main(){
n = rd(), res[p = rd() - 1] = 0;
for(int i = 2; i <= n; ++i){
p = rd();
for(map < ll , ll > :: iterator it = res.lower_bound(p); it != res.end(); res.erase(it++)){
ll j = (*it).first, f = (*it).second;
res[j % p] = max(res[j % p], f + (i - 1) * (j - j % p));
res[p - 1] = max(res[p - 1], f + (i - 1) * ((j + 1) / p * p - p));
}
}
for(map < ll , ll > :: iterator it = res.begin(); it != res.end(); it++)ans = max(ans, n * (*it).first + (*it).second);
printf("%lld", ans);
return 0;
}
标签:log,CF889E,题解,bmod,ans,答案,res,区间
From: https://www.cnblogs.com/Nekopedia/p/18372614