题目描述 Description
某个机器人大赛为优胜者设置了奖励环节,把一条直线路线划分成了N+1个格子,编号0到N,在每个格子上放上一些硬币,并要优胜者控制的机器人在第0个格子出发,走过这条路线,此过程中拾取格子上的硬币,拾到的硬币归此优胜者所有。
小王赢得了机器人武打比赛的冠军,来到了此奖励环节。然而他的机器人刚刚经历一场恶战,出现了故障,导致这个机器人一步只能向前走P到Q之间的整数格,即原先在第i格上,下一步只能走到格子区间[i+P,i+Q]的整数格上。
如果你是小王,你已经知道了每个格子上的硬币数和P、Q ,你能获得的硬币最多有多少?(只要机器人位置超过了N,就算走出了路线。)
输入描述 Input Description
第一行有三个整数N,P,Q,用空格隔开
第二行有N+1个整数,用空格隔开,第i个数表示编号为i-1的格子上的硬币数量,而第1个数是起点的硬币数,只能是0。
输出描述 Output Description
一个整数,表示可拾取的最大硬币数。保证不超过2^31-1。
样例输入 Sample Input
5 2 3
0 12 3 11 7 -2
样例输出 Sample Output
11
数据范围及提示 Data Size & Hint
对于60%的数据:N≤10,000
对于100%的数据:N≤200,000
对于所有数据 A[i]≤2,000且1≤P≤Q≤200
#include <iostream>
#include <cstdio>
using namespace std;
int a[200005];
long long m, n, p, q, ans;
int main(){
cin >> n >> p >> q;
for(int i=0; i<=n; i++) cin >> a[i];
while(true){
if(m+q>n) {
cout<< ans;
return 0;
}
int jj, kk=-1;
for(int i=m+p; i<=m+q; i++) {
if(a[m+i] > kk) {
kk = a[m+i];
jj = i;
}
}
m+=jj;
ans+=kk;
}
return 0;
}
全WA,求救急