题解 CF1389B 【Array Walk】

简要题意:

你前面一共有

nn

n 个格子,每个格子都有它的分值

axa_x

ax​。当你到达第

xx

x 个格子就能获得第

xx

x 个格子的得分

axa_x

ax​。

初始时你站在第

11

1 个格子,每一次移动你可以选择向左或向右,特别地,向左移动的次数不能超过

zz

z。

现在,请问你正好走了

kk

k 步后,最大得分是多少?

这道题比赛时,我先写了个正解,结果发现出了点问题,然后不知道怎么想的,去写了

22

2 个显然是假的的贪心,然后又跑回去重新按照第

11

1 次的思路写了一遍,然后就过了。于是我就丢人地做了

5050

50 分钟

BB

B,导致没来得及写完

DD

D。

这道题考虑这样一件事,我们没走一步,虽然位置并不一定单调不降,但是向左走的步数和总共走的步数一定是单调不降的,换句话说就是这

22

2 个量无后效性,这就是本题的突破口。

我们知道向左走的步数和总共走的步数就可以知道当前在哪个格子,然后我们再来决定这步是从哪里转移过来的,上一步是向右走的还是向左走的。

思路大概就是这样,希望一些细节大家还是自己推一下,还是比较复杂的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
const int MAXN=1e5+10;
int a[MAXN],f[6][MAXN];
int work(){
int n,k,z;
read(n);read(k);read(z);
for(int i=1;i<=n;i++)read(a[i]);
f[0][0]=a[1];
for(int i=0;i<=z;i++)
for(int j=1;j<=k;j++){
f[i][j]=f[i][j-1]+a[j-i*2+1];
if(i!=0)f[i][j]=max(f[i][j],f[i-1][j-1]+a[j-i*2+1]);
}
int ans=0;
for(int i=0;i<=z;i++)ans=max(ans,f[i][k]);
cout<<ans<<endl;
return 0;
}
int main(){
int T;read(T);
while(T--)work();
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

题解 CF1389B 【Array Walk】

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 题解 CF1389B 【Array Walk】
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏