Difference between revisions of "XVII Open Cup named after E.V. Pankratiev. Grand Prix of Moscow Workshops"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== 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 (+)...") |
Xiejiadong (talk | contribs) |
||
| Line 14: | Line 14: | ||
Solved by Xiejiadong. 2:05 (+) | 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 == | == Problem E == | ||
Latest revision as of 09:43, 26 October 2019
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 (+)