地上有n个格子,每个里面都有一些铜币。小明目前站在第一格,他每走一步能前进m-1格,或者m格,或者m+1格。请问他最多能捡到几个铜币。 注意:并不一定每一格都可以走到
我的代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1009;
int x[N];//每一格金币的数量
int f[N];//f[i]表示共i格时能捡到最多的金币数
bool vst[N];//记录是否访问过该店
/*
n=12,m=4,m-1=3,m+1=5
i=1,2,3,4,5,6
x[i]=1,1,1,5,4,4,1,2,4,3,2,4
f[i]=1,1,1,6,5,5
*/
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>x[i];
f[i]=x[i];
}
vst[1]=1;
for(int i=1;i<=n;i++){
if(i>m-1)f[i]=vst[i-m+1]*f[i-m+1]+x[i];
else if(i>m) f[i]=max(vst[i-m]*f[i-m],vst[i-m+1]*f[i-m+1])+x[i];
else if(i>m+1) f[i]=max(vst[i-m+1]*f[i-m+1],max(vst[i-m]*f[i-m],vst[i-m-1]*f[i-m-1]))+x[i];
}
cout<<*max_element(f+1,f+1+n);
return 0;
}