XVII Open Cup named after E.V. Pankratiev. Grand Prix of Moscow Workshops

Problem A

Solved by Kilo_5723. 4:40 (+8)

Problem B

Solved by Weaver_zhu. 3:08 (+)

Problem C

Unsolved.

Problem D

Solved by Xiejiadong. 2:05 (+)

题意：要将 $n$ 个数分成若干个区间，每个区间的长度必须在 $[l,r]$ 内，要求所有区间中区间和是正的数量 - 区间和是负的数量最大。

题解：可以很显然的得到 dp 方程 : 用 $f[i]$ 表示到第 $i$ 位可以获得的最大代价，那么 $f[i]=max_{j=i-r}^{i-l}f[j]+val(i,j)$ ，其中 $val(i,j)$ 是区间和的正负性决定的 $-1/0/1$ 。

优化转移方式，考虑对于前缀和排序，这样的话，每次转移都可以通过一个区间的 max 来转移。

对于不合法的转移位置设做 $-inf$ 即可。

可用的转移区间用滑动窗口来维护，每次修改边界上的位置即可。

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Kilo_5723. 0:13 (+)

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 0:56 (+)

Problem J

Solved by Weaver_zhu. 3:02 (+)

Problem K

Solved by Kilo_5723. 0:30 (+)