JZOJ 4249. 【五校联考7day1】游戏——斜率优化

原题

WYF从小就爱乱顶，但是顶是会造成位移的。他之前水平有限，每次只能顶出k的位移，也就是从一个整点顶到另一个整点上。我们现在将之简化到数轴上，即从 一个整点可以顶到与自己相隔在k之内的数轴上的整点上。

现在WYF的头变多了

，于是他能顶到更远的地方，他能顶到任意整点上。现在他在玩一个游戏，这个游 戏里他只能向正方向顶，同时如果他从i顶到j，他将得到a[j] * (j - i)的分数，其中a[j]是j点上的分数，且要求j > i, 他最后必须停在n上。
现给出1～n上的所有分数，原点没有分数。他现在在原点，没有分。WYF想知道他最多能得多少分。
吐槽：头变多了？？？

题目大意
给你一个长度为n的序列A，求$\sum^{b_i>b_j(i>j,b_0=0)}_{i=1}A_{b_i}*(b_i-b_{i-1})$∑i=1bi​>bj​(i>j,b0​=0)​Abi​​∗(bi​−bi−1​) 的最大值。

Input

第一行一个整数n。
第二行有n个整数，其中第i个数表示a[j]。

Output

一个整数，表示WYF最多能得到的分数。

Sample Input

3
1 1 50

Sample Output

150

Data Constraint

对于60%的数据，n<=1000；
对于100%的数据，n<=100000,0<=a[j]<=50。

几个显然的事实

1. 这题肯定用DP
2. $O(n^2)$O(n2)过不了（这是废话）
   所以要优化

我一开始只打出了$O(n^2)$O(n2)的暴力（相对于正解，应该算吧）
然后想办法优化。
四边形不等式？？拉倒，肯定不是。
斜率优化？？
之前■■■大佬说过

“斜率优化不能随便用，要满足决策单调性，至于决策单调性是什么，不跟你们解释了”

EMMM。。。好像不满足
姑且认为不能用。。
后来还想到二分，三分什么的，
直到脑海里浮现出这样一幅画面

$即F_i=F_j+a_i(i-j)&gt;F_k+a_i(i-k)\;(k&lt;j&lt;i \land a_j,a_k&gt;a_{[j+1,i]})$即Fi​=Fj​+ai​(i−j)>Fk​+ai​(i−k)(k<j<i∧aj​,ak​>a[j+1,i]​)
所以$F_i$Fi​一定是从最大的，满足$(j&lt;i\land a_j&gt;a_{[j+1,i]})$(j<i∧aj​>a[j+1,i]​)的$j$j转移而来的。

可以用单调栈维护！(虽然我还不知道我打的优化是什么）

等等，为什么长得那么像维护凸包的思路，$a_i$ai​还越来越小

难道这是■率■化？？？

似乎那位大佬的话可以丢一边，暂时不管了。

$当F_j+a_i(i-j)&gt;F_k+a_i(i-k)\;(k&lt;j&lt;i \land a_j,a_k&gt;a_{[j+1,i]})$当Fj​+ai​(i−j)>Fk​+ai​(i−k)(k<j<i∧aj​,ak​>a[j+1,i]​)
$F_j-F_k&gt;a_i(j-k)$Fj​−Fk​>ai​(j−k)
$即\frac{F_j-F_k}{j-k}&gt;a_i时，$即j−kFj​−Fk​​>ai​时，
$选F_j更优$选Fj​更优
$\frac{F_j-F_k}{j-k}越接近a_i,\frac{F_j-F_k}{j-k}越小\\F_j越优，但必须满足\frac{F_j-F_k}{j-k}&gt;a_i$j−kFj​−Fk​​越接近ai​,j−kFj​−Fk​​越小Fj​越优，但必须满足j−kFj​−Fk​​>ai​
若把$(j,F_j)$(j,Fj​)和$(k,F_k)$(k,Fk​)看作点
那上面这个和斜率公式$\frac{Y_1-Y_2}{X_1-X_2}$X1​−X2​Y1​−Y2​​一模一样了。
如图，横坐标表示$i$i,纵坐标表示$F_i$Fi​

直线DG的斜率为$a_i$ai​
而$F_i=F_{D的横坐标}+a_i(i-D的横坐标)$Fi​=FD的横坐标​+ai​(i−D的横坐标)
DE，EF的斜率都比DG小，即使加入一条相同斜率的直线，
接在F上，对后面的贡献也不如DG
同时对$F_i$Fi​也没有贡献。
直接弹栈弹掉。

这就是 斜率优化

时间复杂度$O(n)$O(n)

至于斜率优化的限制，

转移方程必须可以恒等变形为直线解析式，求出斜率

至于决策单调性，这题似乎不满足。
如数据

3
2 1 3

但需要满足对于
有决策$k，j(k&lt;j)$k，j(k<j)
对于所有$i(i&gt;j)$i(i>j)
要么k永远比j优
要么j永远比k优

#include<cstdio>
#include<cstring>
using namespace std;
int a[100010],f[100010];
int ma[100010];
int stack[100010],top=0;
int main()
{
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	memset(f,0,sizeof(f));
	int n,i,j,l,r,m1,m2;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	if(n<=1000)
	{
		for(i=1;i<=n;i++)
		{
			for(j=0;j<i;j++)
			{
				if(f[j]+a[i]*(i-j)>f[i]) f[i]=f[j]+a[i]*(i-j);
			}
		}
	}
	else
	{
		ma[0]=0;a[0]=2147483647;top=0;
		stack[0]=0;
		for(i=1;i<=n;i++)
		{
			while(a[i]>a[stack[top]]) top--;
			ma[i]=stack[top];
			top++;stack[top]=i;
		}
		for(i=1;i<=n;i++)
		{
			f[i]=f[ma[i]]+(i-ma[i])*a[i];
		}
	}
	printf("%d\n",f[n]);
	return 0;
}