JZOJ4249.【五校联考7day1】游戏(贪心大法好)
Description
WYF从小就爱乱顶,但是顶是会造成位移的。他之前水平有限,每次只能顶出k的位移,也就是从一个整点顶到另一个整点上。我们现在将之简化到数轴上,即从 一个整点可以顶到与自己相隔在k之内的数轴上的整点上。现在WYF的头变多了,于是他能顶到更远的地方,他能顶到任意整点上。现在他在玩一个游戏,这个游 戏里他只能向正方向顶,同时如果他从i顶到j,他将得到a[j] * (j - i)的分数,其中a[j]是j点上的分数,且要求j > i, 他最后必须停在n上。
现给出1~n上的所有分数,原点没有分数。他现在在原点,没有分。WYF想知道他最多能得多少分。
Input&Output
第一行一个整数n。
第二行有n个整数,其中第i个数表示a[j]。
一个整数,表示WYF最多能得到的分数。
Example
input
3
1 1 50
output
150
Data
对于60%的数据,n<=1000;
对于100%的数据,n<=100000,0<=a[j]<=50。
Solution
60%:枚举
100%:对于到达的每个点,若要知道应该从哪个点过
来,则要比较从两个不同地方过来的答案进行比较。最后比较式整理成类似于(f[i] – f[j])/(i – j) > ? 的形式。之后可以将(i, f[i])变为二维上的一点,比较式就成为了两点间的斜率是否大于一个数。由于 i 是从小到大枚举的则计算出一个 f[i]时就把它插入到二维平面里,之后只需维护斜率下降的一段(斜率上升的一段不需要考虑),用栈来存储点,维护凸包总时间复杂度为 O(n),找最好节点用二分。总时间复杂度为O(n*log(n))。
其实,说了真么多-----------------------------------------------------------------------------以上都是废话
最最最简单通俗易懂的办法
贪心!!!
我们从后往前扫,只要扫到一个比当前位置i大的a[j]就可以更新答案,这样保证ans最优
感性理解一下
黑色曲线比蓝色直线的方案要优
所以。。。
还要我怎么解释呢?
Code
#include<cstdio>
using namespace std;
int n,a[1100000],curr;
long long ans=0;
inline int read()
{
int x=0,f=0; char c=getchar();
while (c<'0' || c>'9') f=(c=='-') ? 1:f,c=getchar();
while (c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return f ? -x:x;
}
int main()
{
freopen("game.in","r",stdin);
freopen("game.out","w",stdout);
n=read();
for(int i=1;i<=n;++i)a[i]=read();
curr=n;
for(int i=n;i>=0;--i)
if(a[i]>a[curr]){ans+=(curr-i)*a[curr];curr=i;}
ans+=curr*a[curr];
printf("%lld",ans);
return 0;
}