求助站外题
  • 板块学术版
  • 楼主youzhigui_nie
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/20 21:21
  • 上次更新2023/11/3 02:22:14
查看原帖
求助站外题
756163
youzhigui_nie楼主2023/8/20 21:21

地上有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; 
} 
2023/8/20 21:21
加载中...