AtCoder Beginner Contest 128 F - Frog Jump

题意

有一只青蛙，有\(0, 1, \cdots, N - 1\)个荷叶。每个荷叶上有权值\(s_i\)。

选定\(A\), \(B\)，初始分数为\(0\)。 当前位置为\(x\)：对于\(y = x + A\)： 如果\(y = N - 1\)，游戏结束。如果\(y \neq N - 1\)，但是\(y\)这个荷叶存在，那么分数增加\(s_i\)，并且这片荷叶消失。如果\(y \neq N - 1\)，但是\(y\)这个荷叶不存在，那么分数减去\(10^{100}\)，游戏结束。对于\(y = x - B\)： 如果\(y = N - 1\)，游戏结束。如果\(y \neq N - 1\)，但是\(y\)这个荷叶存在，那么分数增加\(s_i\)，并且这片荷叶消失。如果\(y \neq N - 1\)，但是\(y\)这个荷叶不存在，那么分数减去\(10^{100}\)，游戏结束。 问选定最优的\(A\)、\(B\)的情况下，得到的最高分数为多少？

思路

我们考虑，选定了\(A\)、\(B\)后，青蛙的行走路线为：\[ \begin{eqnarray*} 0, A, A - B, A + (A - B), 2(A - B), \cdots, K(A - B), A + K(A - B) \end{eqnarray*} \] 我们令\(C = A - B\)：\[ \begin{eqnarray*} 0, A, C, A + C, 2C, \cdots, KC, A + KC \end{eqnarray*} \] 显然有：\(A + KC = N - 1\)：\[ \begin{eqnarray*} 0, N - 1 - KC, C, N - 1 - (K - 1)C, 2C, \cdots, KC, N - 1 \end{eqnarray*} \] 那么当\(K\)、\(C\)确定的时候，行走路线就已经确定。 并且有一个限制条件为\(KC < N\)，那么显然枚举\(K\)、\(C\)是\(O(nlogn)\)的。 并且我们发现，当我们固定\(C\)，递增\(K\)的时候，行走路线的变化是这样的：\[ \begin{eqnarray*} &&0, N - 1\\ &&0, N - 1 - C, C, N - 1\\ &&0, N - 1 - 2C, C, n - 1 - C, 2C, N - 1\\ \end{eqnarray*} \] 每次增加的是\(N - 1 - KC\)和\(KC\)，这两个点，只需要加上就好了，并且要注意判断是否走到重复的点上了。

代码

#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 int n; ll s[N]; int used[N]; int main() { while (scanf("%d", &n) != EOF) { for (int i = 0; i < n; ++i) { scanf("%lld", s + i); } memset(used, 0, sizeof used); ll res = 0; for (int C = 1; C <= n; ++C) { ll tmp = 0; for (int k = 1; 1ll * k * C < n; ++k) { int a = k * C; int b = n - 1 - k * C; int A = b, B = b - C; if (A <= 0 || B <= 0) break; if (a < 0 || a >= n || b < 0 || b >= n || a == b) break; if (used[a] == C || used[b] == C) { break; } used[a] = C; used[b] = C; tmp += s[a]; tmp += s[b]; res = max(res, tmp); } } printf("%lld\n", res); } return 0; }

转载于:https://www.cnblogs.com/Dup4/p/10929996.html