古老的牛市,遗迹的天梯(DP)

标签: DP

在这里插入图片描述

思路:很明显是个DP,我们用dp[i]表示上到第i阶天梯所需的最小步数,我发现第i阶天梯的最小步数是有2种办法得到的,第一种是如果天梯高度之间差一我们从上一层天梯走一步到这一层dp[i]=min(dp[i],dp[i-1]),第二种是我们先退m阶到j阶,然后一个超级跳到这个j阶到i阶 dp[i]=min(dp[i],dp[j]+m+1)然后我们更像题意判断一下,dp[j]+(1<<m)最多能跳到多少阶

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
const int mod=998244353;
const int N=2e6+10;
const int inf=0x7f7f7f7f;


ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
    return a*(b/gcd(a,b));
}

template <class T>
void read(T &x)
{
    char c;
    bool op = 0;
    while(c = getchar(), c < '0' || c > '9')
        if(c == '-')
            op = 1;
    x = c - '0';
    while(c = getchar(), c >= '0' && c <= '9')
        x = x * 10 + c - '0';
    if(op)
        x = -x;
}
template <class T>
void write(T x)
{
    if(x < 0)
        x = -x, putchar('-');
    if(x >= 10)
        write(x / 10);
    putchar('0' + x % 10);
}
int a[N],dp[N];
int main()
{
    SIS;
    int n;
    cin>>n;
    memset(dp,inf,sizeof dp);
    for(int i=1;i<=n;i++)
        cin>>a[i];
    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);
       for(int j=1;j<i;j++)
       {
           int m=i-j;
           int h=1<<j;
           int pos=1;
           while(pos<n&&a[pos+1]<=a[m]+h) pos++;

           dp[pos]=min(dp[pos],dp[i]+j+1);
       }
    }
    if(dp[n]!=inf)cout<<dp[n];
    else cout<<-1;




    return 0;
}


版权声明:本文为qq_43619680原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_43619680/article/details/107285744

智能推荐

PoolThreadCache

缓存构成   PoolThreadCache的缓存由三部分构成:tiny、small 和 normal。 tiny   缓存数据大小区间为[16B, 496B]数据,数组长度为32,根据数据大小计算索引的办法:数据大小除以16,如下代码所示: small   缓存数据大小区间为[512B, 4KB]数据,数组长度为4,根据数据大小计算索引的办法:数据大小除以512,然后log2得到指数,如下代码所...

Intellij IDEA 搭建Spring Boot项目(一)

Intellij IDEA 搭建Spring Boot项目 标签(空格分隔): SpringBoot JAVA后台 第一步 选择File –> New –> Project –>Spring Initialer –> 点击Next  第二步 自己修改 Group 和 Artif...

CentOS学习之路1-wget下载安装配置

参考1: https://blog.csdn.net/zhaoyanjun6/article/details/79108129 参考2: http://www.souvc.com/?p=1569 CentOS学习之路1-wget下载安装配置 1.wget的安装与基本使用 安装wget yum 安装软件 默认安装保存在/var/cache/yum ,用于所有用户使用。 帮助命令 基本用法 例子:下载...

深入浅出Spring的IOC容器,对Spring的IOC容器源码进行深入理解

文章目录 DispatcherServlet整体继承图 入口:DispatcherServlet.init() HttpServletBean.init() FrameworkServlet.initServletBean() 首先大家,去看Spring的源码入口,第一个就是DispatcherServlet DispatcherServlet整体继承图 入口:DispatcherServlet....

laravel框架的课堂知识点概总

1. MVC 1.1 概念理解 MVC全名是Model View Controller,是模型(model)-视图(view)-控制器(controller)的缩写,一种软件设计典范,用一种业务逻辑、数据、界面显示分离的方法组织代码,将业务逻辑聚集到一个部件里面,在改进和个性化定制界面及用户交互的同时,不需要重新编写业务逻辑 MVC 是一种使用 MVC(Model View Controller ...

猜你喜欢

Unity人物角色动画系统学习总结

使用动画系统控制人物行走、转向、翻墙、滑行、拾取木头 混合树用来混合多个动画 MatchTarget用来匹配翻墙贴合墙上的某一点,人物以此为支点翻墙跳跃 IK动画类似于MatchTarget,控制两只手上的两个点来指定手的旋转和位置,使得拾取木头时更逼真 创建AnimatorController: 首先创建一个混合树,然后双击 可以看到该混合树有五种状态机,分别是Idle、WalkForward、...

Composer 安装 ThinkPHP6 问题

Composer 安装 ThinkPHP6 问题 先说说问题 一.运行环境要求 二.配置 参考: ThinkPHP6.0完全开发手册 先说说问题 执行ThinkPHP6的安装命令 遇到问题汇总如下: 看提示是要更新版本,执行命令更新。 更新之后,再次安装ThinkPHP,之后遇到如下问题。 尝试了很多方法,依然不能解决。其中包括使用https://packagist.phpcomposer.com...

Spring Boot 整合JDBC

今天主要讲解一下SpringBoot如何整合JDBC,没啥理论好说的,直接上代码,看项目整体结构 看一下对应的pom.xml 定义User.java 定义数据源配置,这里使用druid,所以需要写一个配置类 上面指定druid的属性配置,和用户登录的账号信息以及对应的过滤规则: 下面定义数据访问接口和对应的实现: 数据访问层很简单,直接注入JdbcTemplate模板即可,下面再看对应的servi...

html鼠标悬停显示样式

1.显示小手:     在style中添加cursor:pointer 实现鼠标悬停变成小手样式     实例:         其他参数: cursor语法: cursor : auto | crosshair | default | hand | move | help | wait | tex...

Yupoo(又拍网)的系统架构

Yupoo!(又拍网) 是目前国内最大的图片服务提供商,整个网站构建于大量的开源软件之上。以下为其使用到的开源软件信息: 操作系统:CentOS、MacOSX、Ubuntu 服务器:Apache、Nginx、Squid 数据库:MySQLmochiweb、MySQLdb 服务器监控:Cacti、Nagios、 开发语言:PHP、Python、Erlang、Java、Lua 分布式计算:Hadoop...