[练习赛]DP--A题

https://ac.nowcoder.com/acm/contest/5968/A
登上天梯必须要按照它要求的方法,否则就无法登上。它要求的方法为:
1.可以直接登上比当前位置高1个单位高度的天梯。
2.可以从当前阶梯往下退一级天梯(第一级天梯除外)。
3.在连续退k步后,跳跃一次,跳跃的高度不超过2^k。比如说你现在位于第i级天梯,且之前从第i+k级天梯退下来,此时你可以跳到高度不超过(当前高度+ 2^k)的任何一级天梯。每一次跳跃只算一次移动哦!
开始的时候考古小队在第一级天梯。请你计算出最少的移动步数以登上最高一级天梯。

往后退k步,一定是选能跳到的最高的阶梯才能使得步数最少(题目说可以跳到任意一级是迷惑)
dp[i] 表示跳到第i级阶梯的最小步数
状态转移显而易见:
i枚举后退k步:mxHei--能挑到的最高高度

//往后退k步,一定是选能跳到的最高的阶梯才能使得步数最少(题目说可以跳到任意一级是迷惑)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MYINTMAX 0x3f3f3f3f
#define N 205
int a[N],dp[N];//dp[i] 跳到第i级阶梯的最小步数
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        dp[i]=MYINTMAX;
    }
    dp[1]=0;
    for(int i=2;i<=n;++i){
        if(a[i]==a[i-1]+1) dp[i]=min(dp[i],dp[i-1]+1);
        //cout<<dp[i]<<endl;
        for(int k=1;k<i;k++){  // 枚举所有后退的可能性
            int jump = 1<<k;
            int mxHei=i-k;
            while(mxHei<n && a[mxHei+1]<=a[i-k]+jump){  // 找到能到的最高阶梯---
                mxHei++;
            }
            dp[mxHei] = min(dp[mxHei],dp[i]+k+1);
        }
    }
    if(dp[n]>=MYINTMAX) cout<<-1;
    else cout<<dp[n];
}
全部评论

相关推荐

06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
缓解焦虑的最好方法是回家。鼠鼠昨天上午考完了本科阶段的最后一场考试,大概率考得稀烂,但是没多想,考完立马收拾行李,坐上了提前约好的顺风车飞奔回家。虽然家和学校很近,只有一百多公里的路程,但距离上次回家也已经有三四个月了。每次想回家,期间总有考试、毕业设计、面试、实习等等各种各样的原因,没办法回去,待在学校和公司的每一天也都充斥着无形的压力和焦虑。现在终于完成了答辩,考完了试,公司那边也请了假,是时候回去一趟了。没有提前通知爸妈,想给他们一个惊喜。下午提前到了家,他俩还在上班,只好让外公外婆来给我开门。因为我的回家,晚上外婆在厨房格外忙碌,做了满满一大桌子菜,填饱了我天天吃外卖的肚子。晚上也没空...
梦想是成为七海千秋:取决于家庭吧?其实回家更焦虑了,每天起床父母都问实习找好了没简历投递了没今天有没有面试,但是又没有什么结果,玩两下手机父母就会说你看你啥也没找到为什么天天就知道刷手机,怎么不去学习…我现在就希望我能永远在外面实习,报喜不报忧,等拿到一个好offer再回家
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务