Description

WYF从小就爱乱顶，但是顶是会造成位移的。他之前水平有限，每次只能顶出k的位移，也就是从一个整点顶到另一个整点上。我们现在将之简化到数轴上，即从 一个整点可以顶到与自己相隔在k之内的数轴上的整点上。现在WYF的头变多了，于是他能顶到更远的地方，他能顶到任意整点上。现在他在玩一个游戏，这个游 戏里他只能向正方向顶，同时如果他从i顶到j，他将得到a[j] * (j - i)的分数，其中a[j]是j点上的分数，且要求j > i, 他最后必须停在n上。
现给出1～n上的所有分数，原点没有分数。他现在在原点，没有分。WYF想知道他最多能得多少分。

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。

Solution

解法一：DP。设 f [ i ] 表示从0到 i 点中最多能得到的分数。那么f[ i ]=max{ f[ j ] + a[ i ] * ( i - j ) }。可以用斜率优化优化到O(n)。对于到达的每个点，若要知道应该从哪个点过来，则要比较从两个不同地方过来的答案进行比较。最后比较式整理成类似于( f[ i ] – f[ j ] )/( i – j) > ? 的形式。之后可以将( i, f[ i ] )变为二维上的一点，比较式就成为了两点间的斜率是否大于一个数。由于 i 是从小到大枚举的则计算出一个 f[ i ] 时就把它插入到二维平面里，之后只需维护斜率下降的一段（斜率上升的一段不需要考虑），用栈来存储点，维护凸包总时间复杂度为O(n)，找最好节点用二分。总时间复杂度为 O( n*log( n ) )。

解法二：贪心。首先有一个结论，每次走到最大的一个点肯定是最优的。

证明：

设当前在点L,有区间[ L, R ]，其中R这个点是区间[ L , R ]的最大值。

• 如果直接从L一步跳到点R，那么贡献为MAX*( R - L )。
• 若果从L先跳到点i，再从点i跳到点R，那么贡献为 a[ i ]*( i - L ) + MAX*( R - i )。
• 比较两个式子的大小，可将第一个式子化为 MAX*(R - i + i - L)=MAX*( R - i )+MAX*( i - L )。因为MAX>a[ i ]，所以MAX*( i - L )>a[ i ]*( i - L )，所以MAX*( i - L ) + MAX*( R - i )>a[ i ]*( i - L )+MAX*( R - i )。
• 对于跳两步以上的情况类似。
• 证毕。（不写要扣两分）

所以我们可以将a[ i ]排序后每次看看能否跳，能跳就跳，这样就保证跳的是最大的了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
using namespace std;
int n,m,x,ans;
struct node{int x,id;}a[N];
bool cmp(node x,node y){return x.x>y.x;}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].x);
		a[i].id=i;
	}
	sort(a+1,a+1+n,cmp);
	x=0;
	for(int i=1;i<=n;i++){
		if(a[i].id>x){
			ans+=a[i].x*(a[i].id-x);
			x=a[i].id;
		}
	}
	printf("%d\n",ans);
	return 0;
}

---

---

作者：zsjzliziyang 
QQ:1634151125 
转载及修改请注明 
本文地址:https://blog.****.net/zsjzliziyang/article/details/86705304