题目

大意：从左到右有\(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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         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
         
           f[MaxM], g[MaxM]; bool goback; pair
          
            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
           
             Compute(int d, int x, int y) { pair
            
              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
             
               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);#endif i64 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;}