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 (+)