\(\text{Problem}\)

大意就是优化这样一个 \(dp\)

\[f_{i}=\max f[j]+(i-j) \cdot (i-j-1)
\]

\(L[i] \le j < i,n\le 5 \times 10^6\)

\(L[i]\) 给出且满足 \(L[x] \le L[x+1]\)

\(\text{Solution}\)

本做法经大佬指点

\(O(n \log n)\) 时限有 \(2.5s\) 且 \(\log\) 来源于树状数组是可以过的

当然本题存在线性做法（然而没懂）

显然斜率优化，最大值维护上凸包

然而你会发现 \(L\) 的限制很可恨，对于入队的点，维护凸包时弹掉的点可能是以后的最优决策（因为\(L\)可以让你取不到没限制时的最优点，不得不往后选在 \(L\) 范围内的点，而这些点可能被维护凸包时弹掉了）

但要明确一点，如果你把可以用的决策点合成一块后维护上凸包，就可以用常规斜率优化弹点寻找最优点

那么我们如何快速把 \([L[i],i)\) 的所有决策提出来维护凸包？

再明确一件事，把 \([L[i],i)\) 分成连续的几块，对每块的最优值取最大值是等价于整块的最优值的（显然）

那么如何优秀地分块

注意到树状数组本身就是个前缀和，且拆成了 \(\log\) 块，可以让树状数组上每个点 \(x\) 维护一个区间的凸包（每个点维护个单调栈，开 \(\text{vector}\)）

本题维护后缀和

这样就可以成功了

\(\text{Code}\)

#include <cstdio>

#include <vector>

#include <iostream>

#define LL long long

#define re register

using namespace std;

const int N = 5e6 + 5;

int n, L[N];

LL f[N];

inline int read(int &x)

{

	x = 0; char ch = getchar();

	while (!isdigit(ch)) ch = getchar();

	while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar();

}

inline double slope(int j, int k)

{

	return 1.0 * (f[j] + 1LL * j * j + j - f[k] - 1LL * k * k - k) / (j - k);

}

struct Stack{

	vector<int> Q;

	inline int size(){return Q.size();}

	inline int top1(){return Q[Q.size() - 1];}

	inline int top2(){return Q[Q.size() - 2];}

	inline void pop(){Q.pop_back();}

	inline void push(int x){Q.push_back(x);}

};

struct BIT{

	Stack t[N];

	inline int lowbit(int x){return x & (-x);}

	inline LL calc(int i, int j)

	{

		return f[j] + 1LL * (i - j) * (i - j - 1);

	}

	inline LL query(int x, int k)

	{

		LL res = 0;

		for(; x <= n; x += lowbit(x))

		{

			while (t[x].size() > 1 && slope(t[x].top2(), t[x].top1()) < k) t[x].pop();

			if (t[x].size()) res = max(res, calc(k / 2, t[x].top1()));

		}

		return res;

	}

	inline void insert(int i)

	{

		for(re int x = i; x; x -= lowbit(x))

		{

			while (t[x].size() > 1 && slope(t[x].top2(), t[x].top1()) < slope(t[x].top1(), i)) t[x].pop();

			t[x].push(i);

		}

	}

}T;

int main()

{

	freopen("jump.in", "r", stdin), freopen("jump.out", "w", stdout);

	read(n);

	for(re int i = 2; i <= n + 1; i++) read(L[i]), ++L[i];

	T.insert(1);

	for(re int i = 2; i <= n + 1; i++) f[i] = T.query(L[i], 2 * i), T.insert(i);

	printf("%lld\n", f[n + 1]);

}

巴特西

NOIP 模拟赛左右横跳

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章

巴特西

NOIP 模拟赛 左右横跳

\(\text{Problem}\)

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章

NOIP 模拟赛左右横跳