[数字dp] hdu 3565 Bi-peak Number

[数字dp] hdu 3565 Bi-peak Number

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

意甲冠军:

为了范围[X,Y],的最大位数的范围内的需求高峰和值多少。

双峰是为了满足一些规定数量 你可以切两 /\ /\ 形式。

思维:

dp[site][cur][ok]  site地点  面的数是cur 状态为ok

ok分为7种

0:前面全部数都是0

1:第一个峰数且仅仅有一个数

2:第一个峰数在峰顶(可上可下)

3:第一个峰数在峰底(可进入下一个峰或者继续往下)

4:同1 是第二个峰数

5:同2 是第二个峰数

6:同3 可是不可进入下一个峰数了

代码:

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"queue"
#include"algorithm"
#include"iostream"
using namespace std;
#define ll unsigned __int64
int dp[30][10][7];
int numx[30],numy[30];
int dfs(int site,int cur,int ok,int fa,int fb)  //由于是大小 所以要在中间推断
{
    if(site==0) return ok==6?0:-1;  //状态6代表成立的数
    if(!fa&&!fb&&~dp[site][cur][ok]) return dp[site][cur][ok];  //都不是边界
    int Min=fa?

numx[site]:0; //上界 int Max=fb?numy[site]:9; //下界 int ans=-1; //初值 for(int i=Min; i<=Max; i++) { int tep=0; if(ok==0&&i) tep=1; //去前导0 else if(ok==1) { if(i>cur) tep=2; //往上走 else tep=-1; //无法走 } else if(ok==2) { if(i>cur) tep=2; //继续上 else if(i==cur) tep=-1; //相等不能走 else tep=3; //往下 } else if(ok==3) { if(i>cur) tep=4; //跳到第二个峰 else if(i==cur) //相等的话0不能跳,由于不能前导0 { if(i) tep=4; else tep=-1; } else tep=3; //继续下 } else if(ok==4) //下同上 { if(i>cur) tep=5; else tep=-1; } else if(ok==5) { if(i>cur) tep=5; else if(i==cur) tep=-1; else tep=6; } else if(ok==6) { if(i>=cur) tep=-1; //最后仅仅能下不能跳了 else tep=6; } if(tep!=-1) { int sum=dfs(site-1,i,tep,fa&&i==Min,fb&&i==Max); //这位放完 后面的最大值 if(sum!=-1) ans=max(ans,sum+i); //加上这位比大小 } } if(!fa&&!fb) dp[site][cur][ok]=ans; //不是边界保存值 return ans; }int main(){ int t,cas=1; cin>>t; memset(dp,-1,sizeof(dp)); while(t--) { ll x,y; scanf("%I64u%I64u",&x,&y); //注意2^64次方 要用无符号64位读入 int cnt=0; while(y) { cnt++; numx[cnt]=x%10; x/=10; numy[cnt]=y%10; y/=10; } int ans=dfs(cnt,0,0,1,1); printf("Case %d: %d\n",cas++,ans==-1?0:ans); } return 0;}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117374.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 2020年追番报告_2021是什么年

    2020年追番报告_2021是什么年文章目录一,轻松猛男可爱萌系动漫(日常,轻松,治愈)二,热血战斗类型(1)骨王系列(龙傲天)(2)炮姐系列(B站镇站之宝)(3)mappa(霸权社作品)回战+巨人(神作)出圈作品(4)国漫优秀作品,三体IP+优秀制作(5)老番系列三,催泪神作一,轻松猛男可爱萌系动漫(日常,轻松,治愈)高分恋爱题材动漫,搞笑日常,不用动脑恋爱题材,无刀,极其酸,B站弹幕也很有趣异世界类型,盾娘天然呆+高玩好友组合,轻松愉快无刀异世界类型,萌王史莱姆龙傲天的故事轻松日常,社畜小林和龙女仆的轻松日常

  • 通过@MapperScan源码了解Spring自定义注解扫描器[通俗易懂]

    通过@MapperScan源码了解Spring自定义注解扫描器[通俗易懂]我们在使用springboot整合MyBatis时,需要在启动类上添加上@MapperScan注解,并写入mapper接口的包路径,然后我们就能通过从springIOC容器中取对应的mapper的Bean来进行持久化操作了,那么@MapperScan是如何将mapper接口实例化并注入到SpringIOC容器中的呢?首先搭建一个springboot项目,引入mybatis和mysql的相…

  • cdrecord光盘烧录工具

    cdrecord光盘烧录工具

  • JavaScript闭包函数

    JavaScript闭包函数JavaScript闭包函数1概述2词法作用域3闭包1概述一个函数和对其周围状态(词法环境)的引用捆绑在一起(或者说函数被引用包围),这样的组合就是闭包(closure)。也就是说,闭包让你可以在一个内层函数中访问到其外层函数的作用域。在JavaScript中,每当创建一个函数,闭包就会在函数创建的同时被创建出来。2词法作用域请看这段代码:functioninit(){varname=”Mozilla”;//name是一个被init创建的局部变量

  • Java学习之Spring Boot入门

    Java学习之SpringBoot入门0x00前言学习完ssm的整合后,开始来学习SpringBoot,在前面学习Spring的时候会发现使用Spring开发中配置Spring的环境会非常的

    2021年12月12日
  • Java设计模式之创建型:原型模式

    Java设计模式之创建型:原型模式

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号