hdu 3652 B-number(数字dp)

hdu 3652 B-number(数字dp)

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

http://acm.hdu.edu.cn/showproblem.php?

pid=3652

大致题意:”B-number“即一个整数含有子串”13″且被13整除。求1-n之间这种数的个数。


思路:有两个限制条件:含有子串“13”和能被13整除。

那么设dp[site][mod][flag]。表示到第site位对13取余为mod且标记为flag的数的个数。flag表示是否含有子串”13″。

然后进行记忆话搜索。


#include <stdio.h>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-8
#define PI acos(-1.0)
using namespace std;

int dp[15][15][5];
int dig[15];
//flag = 0表示前一个不是1,flag = 1表示前一个是1。flag = 2表示出现"13"。

int dfs(int site, int mod, int flag, int up){ if(site == 0) return mod == 0 && flag == 2; //当mod为0且有"13"时。返回1 if(!up && dp[site][mod][flag] != -1)//记忆化 return dp[site][mod][flag]; int len = up ?

dig[site] : 9; int ans = 0; for(int i = 0; i <= len; i++) { int tmod = (mod*10 + i) % 13; int tflag = flag; if(flag == 1 && i == 3) tflag = 2; else if(flag == 0 && i == 1) tflag = 1; else if(flag == 1 && i != 1) tflag = 0; ans += dfs(site-1, tmod, tflag, up && (i == len) ); } if(!up) dp[site][mod][flag] = ans; return ans;}int cal(int n){ int cnt = 0; while(n) { dig[++cnt] = n % 10; n /= 10; } memset(dp,-1,sizeof(dp)); return dfs(cnt,0,0,1);}int main(){ int n; while(~scanf("%d",&n)) { printf("%d\n",cal(n)); } return 0;}

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

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

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

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

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

(0)


相关推荐

  • kl散度和交叉熵的区别_散度的概念

    kl散度和交叉熵的区别_散度的概念通用的说,熵(Entropy)被用于描述一个系统中的不确定性(theuncertaintyofasystem)。在不同领域熵有不同的解释,比如热力学的定义和信息论也不大相同。要想明白交叉熵(CrossEntropy)的意义,可以从熵(Entropy)-&gt;KL散度(Kullback-LeiblerDivergence)-&gt;交叉熵这个顺序入手。当然,也有多种解释方法…

    2022年10月23日
  • pyside2界面美化_手机音量进度条 插件

    pyside2界面美化_手机音量进度条 插件前言在我们进行自动化测试的时候,用例往往是成百上千,执行的时间是几十分钟或者是小时级别。有时,我们在调试那么多用例的时候,不知道执行到什么程度了,而pytest-sugar插件能很好解决我们的痛点。

  • CSS 图片去色处理

    CSS 图片去色处理说到对图片进行处理,我们经常会想到PhotoShop这类的图像处理工具。作为前端开发者,我们经常会需要处理一些特效,例如根据不同的状态,让图标显示不同的颜色。或者是hover的时候,对图片的对比度,阴影进行处理。//黑白色img{transition:all.3sease;filter:grayscale(100%);opacity:.6;}//正常颜色img:hover{filter:none;opacity:1;

  • springboot面试大全

    springboot面试大全https://blog.csdn.net/Kevin_Gu6/article/details/885474241SpringBoot有哪些优点?起步依赖自动配置应用监控2springboot的核心配置文件,以及加载顺序?bootstrap(.properties/.yml)用来加载系统相关的配置application(.properties/.yml)用来…

  • windows下面编译ucosII操作系统

    windows下面编译ucosII操作系统       ucos是一款在嵌入式系统上应用的实时操作系统,为了调试和学习(我们部门负责DSP、MCU、ARM到服务器的各种程序),有必要再windows下面模拟运行,我在一个德国网站上找到了一份移植过的代码,经过我的小小修改,已经可以用VS2010和Dev-C++(MinGw编译器)上编译运行。 运行过程中发现2个编译器编译出来的程序运行结果并不相同,看来2种编译器在实现…

  • jar包反编译工具

    jar包反编译工具在学习和开发JAVA项目中,我们经常会用到第三方提供的一些jar。使用这些第三方工具包,可以提高我们开发的效率,缩短开发的时间。有的第三方工具,提供具体的使用说明和源代码,有时有的却不提供源代码,使用说明也不是很具体,这对我们使用就非常不方便。  有道是,知其然才知其所以然。有时候,我们…

发表回复

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

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