Fork me on GitHub

2018CCPC网络预选赛1007(hdu6444) 单调队列

Neko’s loop

问题分析

题意:给一个元素个数为$n$的环,选定任意一个起点$i$后,每次可以往前跳$(i+k)\%n$,然后会相应得到$a_i$的收益,问跳$m$次后总收益可以达到$s$(可以提前停止),在开始之前至少需要身上需要有多少收益。

显然这样选定一个起点后不断往前跳,所获得的$a_i$会形成一个环。

那么我们就可以把所有环找出来,通过枚举环的起点来找每个环可以获得的最大收益。问题就转化成求每个环的长度为$m$的最大子段和了。

我们用$cnt = \frac{len}{m}(len表示循环节长度)$代表需要跑几次循环节,用$ret = len \% m$代表剩余步数。
但是我们要注意两点。
首先,如果循环节的总收益为负,那么我们直接求一个不超过$m$的最大子段和就可以了。因为跑再更多次只会收益变得更小。
其次,如果$len>m$,我想很多人可能就会直接$cnt * 循环节总收益 +剩余(len\% m)所能获得最大总收益$,这就是本题的坑点了。因为题目告诉了我们可以提前停止,如果最后一圈有负数,我们可以跑完正数的那一部分,剩下的负数不跑了。
就比如序列为$-2,-5,-7,20$,那么我们可以跑完$cnt-1$圈,再跑个$20$就够了。所以我们真正能确定的是前$cnt-1$前所能获得的最大收益,剩下的我们拿出来单独跑。

但是呢,还是要注意,我们跑剩余的时候,长度为$len+(len\%m)$,然后最后一步能跑到的范围为$(len-1,3*len)$,因此我们需要开三倍的数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5+10;
const LL inf = 1e18;
LL n,m,k,s,a[N],sum[N];
bool vis[N];
vector<LL> v[N];

LL solve(int d,int n,LL m) {
LL ans = 0;
memset(sum, 0, sizeof sum);
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + v[d][i - 1];
for (int i = n + 1; i <= 2 * n; ++i)
sum[i] = sum[i - 1] + v[d][i - n - 1];
for (int i = 2 * n + 1; i <= 3 * n; ++i)
sum[i] = sum[i - 1] + v[d][i - 2 * n - 1];

deque<int> dq;

for (int i = 1; i <= 3 * n; ++i) {
while (!dq.empty() && sum[dq.back()] > sum[i - 1])
dq.pop_back();
while (!dq.empty() && dq.front() + m < i) //控制子段和长度为m
dq.pop_front();
dq.emplace_back(i - 1);
ans = max(ans, sum[i] - sum[dq.front()]);
}
return ans;
}

int main() {

int T;
scanf("%d", &T);
for (int t = 0; t < T; ++t) {
memset(vis, 0, sizeof vis);
LL ans = -inf;
int tot = 0;
for (int i = 0; i < N; ++i)
v[i].clear();
scanf("%lld%lld%lld%lld", &n, &s, &m, &k);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
//处理循环节
for (int i = 0; i < n; i++) {
if (!vis[i]) {
for (int j = i; !vis[j]; j = (j + k) % n) {
vis[j] = 1;
v[tot].push_back(a[j]);
}
tot++;
}
}
for (int i = 0; i < tot; ++i) {
LL res = 0, tmp = 0;
int len = v[i].size();
for (int j = 0; j < len; ++j)
tmp += v[i][j];
res = solve(i, len, m);
ans = max(ans, res);
//总收益小于0的话就跑一段长度不超过m的最大子段和就可以了
if (tmp < 0)
continue;
LL ret = m % len;
LL cnt = m / len;
tmp = max(cnt - 1, 0LL) * tmp; // cnt-1圈
if (cnt >= 1) ret += len;
res = max(res, solve(i, len, ret) + tmp); //剩下的特判(单独算)
ans = max(ans, res);
}
ans = max(s - ans, 0LL);
printf("Case #%d: %lld\n", t + 1, ans);
}
return 0;
}
0%