第3课 攀登宝塔(《信息学探秘:提高篇》)-2019-06-16.pdf

所需积分/C币:22 2019-06-16 21:12:34 365KB PDF

第3课 攀登宝塔(《信息学探秘:提高篇》)-2019-06-16 第3课 攀登宝塔(《信息学探秘:提高篇》)-2019-06-16
问题描述】 有一天,贝贝做了一个奇怪的梦,梦中他来到一处宝塔,他想要从 塔的外面爬上去。这座宝塔的建造很特别,塔总共有η层,但是每层 的高度却不相同,这造成了贝贝爬过每层的时间也不同。贝贝会用仙 术,每用一次可以让他向上跳一层或两层,这时不会耗费时间,但是 每次跳跃后贝贝都将用完灵力,必须爬过至少一层才能再次跳跃。贝 贝想用最短的时间爬到塔顶,可是他找不到时间最短的方案,所以请 你帮他找到一个时间最短的方案,让他爬到塔顶(可以超过塔高)。 贝贝只关心时间,所以你只要告诉他最短时间是多少就可以了 【输入格式】 第1行一个数n(n≤10000),表示塔的层数; 接下来的n行每行一不超过100的正整数,表示从下往上每层 的所需的时间 输出格式】 个数,表示最短时间。 输入样例】 535184输1 出样例】 分析问题 该问题是利用仙术跳跃和爬行两种方式的不同组合(仙术不 能连续使用),计算到达塔顶所需的最短时间。显然我们以层 为阶段,用f[i]记录到达第i层时所需的最短时间。但此时状态 转移时遇到了问题,因为到达第i层时可以由第i-1层爬到第i层, 也可以爬到第i-1或i2层后再用仙术跳跃到第i层,而f[i-1] f[i-2]仅仅记录到达第i1、i2层的最短时间,并不清楚刚刚 是否使用过仙术跳跃。 学习新知 印无法同时表示最优值和是否刚使用过仙术,因此,我们需要再引入 个变量⑨[,其中们表示跳到第层时花费的最少的时间,g表示爬到 第层时花费的最少时间。我们把上述方法称之为状态拆分”。 通常我们选定的状态应满足以下两点 1.状态必须完全描述出事物的性质,两个不同事物的状态是不同的 2.必须存在状态与状态之间的“转移方程”,以便可以由初始状态逐渐 转化为目标状态。 解决问题 1.问题:按规则跳到塔外后,花费的最少时间。 结论:以每一层为阶段。 2.状态:f[i表示跳到第i层时花费的最少时间,g[i]表示 爬到第i层时花费的最少时间。 3.状态转移方程: fLi]= minigli-1, g[i-21) g[i]=min{g[i-1],fi-1])+ time[i(1≤i≤n) 4.问题的解:min{fn],gn 该算法的时间复杂度为0(n)。 参考程序如下: #include<bits/stdc++h> using namespace std intg[10009],f[10009] intt[100000]; int main( Int n,. cIn>>n, for(i=1;<=n;i++) cin>>t[i; f[o]=0; g[0]=0; for(i=1;<=n;i++) g[]=min(g[i-1],f[i-1])+tj f(1) f[i]=min(g[i-1]g[i-21 else f[=0 cout<<min(f[nlgn]<<endl return 0; 第3课攀登宝塔相关的链接 http://oj.jzagile.com/judgeonline/problem.php?cid=1058&pid=10 http://blog.sinacomcn/s/blog_15c49b5d20102wgo0.html string字符串( string) http://cxsizx.hustoj.com/problem.php?cid=10458pid=7 桐桐的爬山计划( climb) http://noiper.hustoj.com/problem.php?id=1136 http://oj.jzagile.com/judgeonline/problem.php?id=1224 多米诺骨牌( domino) https://blog.csdn.net/ssllyf/article/details/85129316

...展开详情
img
  • GitHub

    绑定GitHub第三方账户获取
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐