注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

抢金块(gold)解题报告  

2015-08-05 10:38:14|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

问题描述

地面上有一些格子,每个格子上面都有金块,但不同格子上的金块有不同的价值,你一次可以跳ST (2ST10) 如果S=2T=4。你就可以跳2步、3步或4步,告诉你这些后,你从第一个格子起跳,必须跳到最后一个格子上,请你输出最多可以获得的金块的总价值。

输入格式

第一行是格子个数;

第二行是ST ,保证T大于S

第三行是每个格子上的金块价值。第一个为第一个格子上的价值,默认从第一个格子起跳,必须跳到最后一个格子上,也就是说第一个格子上的金块和最后一个格子的金块你就可以直接获得了。

输出格式

 输出最多可以获得的金块的总价值。

输入样例

10

2 3

4 5 8 2 8 3 6 7 2 9

输出样例

36

=================================================================

样例说明:

135810

总价值:4+8+8+7+9=36

数据规模

      格子数目<1000

      2≤ST≤10

      每个金块的价值<10000。

=================================================================

        抢金块这题,其实是最基本的动态规划题目了,不过有很多细节问题,下面就来分析一下:

=================================================================

        阶段,以跳到第i格的最大价值为一个阶段。

        子问题与决策,跳到第i格,肯定与是从第i-j格跳过来的(j=S~t),所以从中选个最大值就行了。

        边界,呃……看有没有跳出格子就行了。

=================================================================

         再讲讲细节问题:

         1,如果那个格子是跳不到的,值为0;

         2,必须跳到最后一格;

         3,如果方向是向后看,看后面哪个最大选哪个,就要注意边界;如果方向是向前看,看我能改变谁,这就可以不怎么注意边界了。

=================================================================

#include<cstdio>

#include<fstream>

#include<iostream>

#include<stdlib.h>

#include<cstring>

#include<algorithm>


using namespace std;


int f[2000],a[2000];


int main()

{

freopen("gold.in","r",stdin);

freopen("gold.out","w",stdout);

int n,l,r;

scanf("%d%d%d",&n,&l,&r);

for (int i=0; i<n; i++)

scanf("%d",&a[i]);

for (int i=0; i<n; i++)

{

f[i]+=a[i];

if (i>0 && f[i]==a[i]) continue;     //看看能不能跳到

for (int j=l; j<=r; j++)

 f[i+j]=max(f[i+j],f[i]);        //我能改进谁?

}

if (f[n-1]==a[n-1]) f[n-1]=0;  //能不能跳到最后一格?

printf("%d\n",f[n-1]);

return 0;

}


  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018