Description
WYF從小就愛亂頂，但是頂是會(huì)造成位移的。他之前水平有限，每次只能頂出k的位移，也就是從一個(gè)整點(diǎn)頂?shù)搅硪粋€(gè)整點(diǎn)上。我們現(xiàn)在將之簡(jiǎn)化到數(shù)軸上，即從 一個(gè)整點(diǎn)可以頂?shù)脚c自己相隔在k之內(nèi)的數(shù)軸上的整點(diǎn)上。現(xiàn)在WYF的頭變多了，于是他能頂?shù)礁h(yuǎn)的地方，他能頂?shù)饺我庹c(diǎn)上。現(xiàn)在他在玩一個(gè)游戲，這個(gè)游 戲里他只能向正方向頂，同時(shí)如果他從i頂?shù)絡(luò)，他將得到a[j] * (j - i)的分?jǐn)?shù)，其中a[j]是j點(diǎn)上的分?jǐn)?shù)，且要求j > i, 他最后必須停在n上。
現(xiàn)給出1～n上的所有分?jǐn)?shù)，原點(diǎn)沒有分?jǐn)?shù)。他現(xiàn)在在原點(diǎn)，沒有分。WYF想知道他最多能得多少分。

Input
第一行一個(gè)整數(shù)n。
第二行有n個(gè)整數(shù)，其中第i個(gè)數(shù)表示a[j]。

Output
一個(gè)整數(shù)，表示W(wǎng)YF最多能得到的分?jǐn)?shù)。

Sample Input
3
1 1 50

Sample Output
150

Data Constraint
對(duì)于60%的數(shù)據(jù)，n<=1000；
對(duì)于100%的數(shù)據(jù)，n<=100000,0<=a[j]<=50。

.
.
.
.
.
分析
這道題可以用斜率優(yōu)化貪心來做

.
.
.
.
.
程序：

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

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10458930.html

總結(jié)

以上是生活随笔為你收集整理的【五校联考7day1】游戏的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。