题目

题目链接

大意：从左到右有\(n\)个城市，一开始在城市\(start\)，每一天有两种选择：

• 前往相邻的城市。
• 访问当前城市（每个城市只能访问一次），访问城市\(i\)可以获得\(attraction_i\)的分数。

问：在\(d\)天内最多能获得多少分数。

算法

首先，分成左右两边来做，路线有\(4\)种：

• 往右走
• 往左左
• 现往右再往左
• 先往左再往右

将左右分开做，对于往右走，计算出\(f(i)\)，表示往右走不回头在\(i\)内最大得分；以及\(g(i)\)，表示往右走但是要回到原点在\(i\)天内的最大得分。计算答案时只需要根据上面所说的\(4\)种情况进行枚举\(d\)的分布（即枚举\(i\)天在城市\(start\)右边转，\(d-i\)天在左边转）就可以了。

这里讲讲如何计算\(f\)，那计算\(g\)是类似的。

那如何计算\(f(i)\)呢？

枚举最远到达的城市\(j\)，那么就有\(i-j\)天的时间去访问城市，那当然访问最大的\(i-j\)个城市啦。这个用线段树可以实现求城市\(start\)到城市\(j\)中，得分最大的前\(i-j\)的城市的和。这样求一次\(f(i)\)的复杂度是\(O(n \cdot logn)\)。

那如何求所有的\(f(i)\)呢，有一个神奇的东西：

设\(f'(i)\)为，求\(f(i)\)时，得到最大得分的枚举的那个城市\(j\)。那么对于$ i’ < i \(，有\)f'(i’) \leqslant f'(i)$。这样子，就可以分治了。

现在求\(f(1)\),\(f(2),… ,f(d)\)（\(d\)是最大天数），需要枚举的\(j\)为\(start,…,n\)，设\(m= (1 + d) \text { div } 2\)，用上述方法求出\(f(m)\)。然后递归求\(f(1),f(2),…,f(m-1)\)，注意，此时枚举的\(j\)只是\(start,start+1,…,f'(m)\)，范围缩小了。另外还要递归求\(f(m+1),f(m+2),…,f(n)\)，此时枚举的\(j\)只是\(sf'(m),f'(m)+1,…,n\)。

所以，我们得到一个\(O(n\cdot log^2 n)\)的算法。

代码

写得不好。

#include"holiday.h"
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <assert.h>
using namespace std;#ifdef debug
#define ep(...) fprintf(stderr, __VA_ARGS__)
#else
#define ep(...) assert(true)
#endiftypedef long long int i64;const int MaxN = (int) 1e5 + 3;
const int MaxM = MaxN * 2 + MaxN / 2;
const int MaxT = 262144;struct Node
{
i64 sum;
int cnt;
}T[MaxT];#define idxl (idx << 1)
#define idxr (idx << 1 ^ 1)void Modify(int idx, int L, int R, int x, int t, int val)
{
if (L == R)
{
T[idx].cnt = t;
T[idx].sum = t ? val : 0;
}
else
{
int M = (L + R) >> 1;
if (x <= M) Modify(idxl, L, M, x, t, val);
else Modify(idxr, M + 1, R, x, t, val);
T[idx].cnt = T[idxl].cnt + T[idxr].cnt;
T[idx].sum = T[idxl].sum + T[idxr].sum;
}
}i64 Query(int idx, int k)
{
if (k >= T[idx].cnt) return T[idx].sum;
if (T[idxl].cnt >= k) return Query(idxl, k);
return T[idxl].sum + Query(idxr, k - T[idxl].cnt);
}struct OneSide_struct
{
int n, m;
int A[MaxN];
pair<int, i64> f[MaxM], g[MaxM];
bool goback;pair<int, int> tmp[MaxN];
int rank[MaxN];void Init()
{
for (int i = 0; i < n; i ++)
tmp[i] = make_pair(A[i], i);
sort(tmp, tmp + n);
for (int i = 0; i < n; i ++)
rank[tmp[i].second] = n - i - 1;
}pair<int, i64> Compute(int d, int x, int y)
{
pair<int, i64> ret = make_pair(-1, -1);
for (int i = x; i <= y; i ++)
{
Modify(1, 0, n - 1, rank[i], 1, A[i]);
int rest = d - (goback ? i << 1 : i);
if (rest <= 0) break;
i64 tmp = Query(1, rest);
if (tmp > ret.second)
{
ret.first = i;
ret.second = tmp;
}
}
for (int i = x; i <= y; i ++)
Modify(1, 0, n - 1, rank[i], 0, A[i]);
assert(ret.second != -1);
return ret;
}void Solve(int L, int R, int x, int y, pair<int, i64> ans[])
{
int M = (L + R) >> 1;
ans[M] = Compute(M, x, y);
if (L < M)
Solve(L, M - 1, x, ans[M].first, ans);
if (R > M)
{
for (int i = x; i < ans[M].first; i ++) Modify(1, 0, n - 1, rank[i], 1, A[i]);
Solve(M + 1, R, ans[M].first, y, ans);
}
for (int i = x; i < y; i ++) Modify(1, 0, n - 1, rank[i], 1, A[i]);
}
};long long int findMaxAttraction(int n, int start, int m, int A[])
{
static OneSide_struct R, L;
R.n = 0;
for (int i = start; i < n; i ++)
R.A[R.n ++] = A[i];
R.m = m;
R.Init();R.goback = false;
R.Solve(1, R.m, 0, R.n - 1, R.f);
R.goback = true;
memset(T, 0, sizeof(T));
R.Solve(1, R.m, 0, R.n - 1, R.g);L.n = 0;
for (int i = start - 1; i >= 0; i --)
L.A[L.n ++] = A[i];
L.m = m;
L.Init();if (L.n)
{
L.goback = false;
memset(T, 0, sizeof(T));
L.Solve(1, L.m, 0, L.n - 1, L.f);
L.goback = true;
memset(T, 0, sizeof(T));
L.Solve(1, L.m, 0, L.n - 1, L.g);
}#ifdef debug
for (int i = 0; i < m; i ++)
ep("R %d %lld %lld\n", i, R.f[i].second, R.g[i].second);
ep("\n");
for (int i = 0; i < m; i ++)
ep("L %d %lld %lld\n", i, L.f[i].second, L.g[i].second);
#endifi64 ans = max(R.f[m].second, L.f[m - 1].second);
for (int i = 0; i < m; i ++)
ans = max(ans, R.g[i].second + L.f[m - i - 1].second);
for (int i = 0; i < m - 2; i ++)
ans = max(ans, L.g[i].second + R.f[m - i - 2].second);return ans;
}