2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1 [2021/07/07 11:31] jxm2001 |
2020-2021:teams:legal_string:jxm2001:contest:cf_728_div._1 [2021/07/09 20:24] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== Codeforces Round #706 (Div. 1) ====== | + | ====== Codeforces Round #728 (Div. 1) ====== |
| [[http://codeforces.com/contest/1540|比赛链接]] | [[http://codeforces.com/contest/1540|比赛链接]] | ||
| 行 117: | 行 117: | ||
| 设 $\text{dp}(i,s)$ 表示 $\sum_{j=1}^i a_i=s$ 的情况，$m=\max c_i$，利用差分可以 $O(n^2m)$ 计算答案。 | 设 $\text{dp}(i,s)$ 表示 $\sum_{j=1}^i a_i=s$ 的情况，$m=\max c_i$，利用差分可以 $O(n^2m)$ 计算答案。 | ||
| - | 最后有 $\min\left(\cfrac {-ssb_i}i\right)\le f_1\le \min\left(\cfrac {sc_i-ssb_i}i\right)$，于是有 $\max(f_1)-\min f_1\le m$。 | + | 最后有 $\min\left(\cfrac {-ssb_i}i\right)\le f_1\le \min\left(\cfrac {sc_i-ssb_i}i\right)$，于是有 $\max(f_1)-\min (f_1)\le m$。 |
| 即有效的 $x$ 只有 $O(m)$ 个，最终时间复杂度 $O\left(n^2m^2\right)$。 | 即有效的 $x$ 只有 $O(m)$ 个，最终时间复杂度 $O\left(n^2m^2\right)$。 | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_728_div._1.1625628704.txt.gz · 最后更改: 2021/07/07 11:31 由 jxm2001
