HDU 3652 B-number(数位DP)

HDU 3652 B-number(数位DP)

大家好,又见面了,我是你们的朋友全栈君。

B-number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1231    Accepted Submission(s): 651

 

Problem Description
A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string “13” and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
 
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
 
Output
Print each answer in a single line.
 
Sample Input
13 100 200 1000
 
Sample Output
1 1 2 2
 
Author
wqb0039
 
 
题意
找包含13且被13整除的个数。
 
分析
能被13整除,只需要记录%13的值就好。那么如何找包含13的呢,我们需要记录当前最后一位的值,这样才可以从1 –》13。
dp[i][j][k][z]:i:处理的数位,j:该数对13取模以后的值,k:是否已经包含13,z结尾的数
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
using namespace std;
int dp[12][15][2][10];
int bit[12];
int dfs(int pos,int num,bool t,int e,bool flag)
{
    if(pos==-1)return t&&(num==0);
    if(!flag && dp[pos][num][t][e]!=-1)
        return dp[pos][num][t][e];
    int end=flag?bit[pos]:9;
    int ans=0;
    for(int i=0;i<=end;i++)
        ans+=dfs(pos-1,(num*10+i)%13,t||(e==1&&i==3),i,flag&&(i==end));
    if(!flag)dp[pos][num][t][e]=ans;
    return ans;
}
int calc(int n)
{
    int pos=0;
    while(n)
    {
        bit[pos++]=n%10;
        n/=10;
    }
    return dfs(pos-1,0,0,0,1);
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d",&n)==1)
    {
        printf("%d\n",calc(n));
    }
    return 0;
}


 

 

转载于:https://www.cnblogs.com/fht-litost/p/8973679.html

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

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

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

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

(0)


相关推荐

  • auto.js微信自动回复脚本_微信群助手机器人

    auto.js微信自动回复脚本_微信群助手机器人一、前言整体思路1)找到头像右上角有消息标志的聊天(注意直接跑下面代码的时候请确保聊天界面由此前提)2)点击进入聊天窗口,找到所有消息3)取最后一个消息(最新消息)4)和之前的新消息对比是否发生变化5)新消息推送至API6)收到API消息发送微信v8版本发送消息时,不再显示“发送”按钮了,也就没办法用找到“发送”控件的方法实现发送消息了。尝试用KeyCode(code)方式,发送回车键,发现也无效,原因查了一下好像是需要ROOT还是安卓9以上此方法失效。于是用坐标点击的方式点击键盘上的

  • ubuntu中利用ffmeg将短视频转化为动图.gif.「建议收藏」

    ubuntu中利用ffmeg将短视频转化为动图.gif.「建议收藏」命令:ffmpeg-ss00:00:1-i/home/jiangcm/Pictures/session_gpus_pre.mp4-to00:00:8-r4-vfscale=700:-1/home/jiangcm/Pictures/session_gpus_pre.gif解读:-ss00:00:1:表示从第1秒开始;-i:表示invert,转换,后面跟着转换的视频;-to:表示结束时间;-r4:4帧率;vfscale=700:-1:制定宽度,高度为原来的倍;/ho

  • laravel查询构造器DB还是ORM,这两者有什么区别,各该用在什么场景中

    laravel查询构造器DB还是ORM,这两者有什么区别,各该用在什么场景中

  • 【NVIDIA】Win10 + CUDA10 + cuDNN 安装教程

    【NVIDIA】Win10 + CUDA10 + cuDNN 安装教程目录一、前言二、官方安装教程及软件包1、官方教程2、CUDAToolkit10.0Download3、cuDNNDownload三、Win10安装CUDA10及cuDNN1、CUDA安装2、cuDNN配置3、万事大吉,只欠重启四、一些后事问题1:安装过程中电脑自动重启。问题2:安装完成后找不到CUDA文件夹。一、前言其实听早就接触NV…

  • java 解析xml报文(字符串)「建议收藏」

    java 解析xml报文(字符串)「建议收藏」一:maven:<!–解析xml报文–><dependency><groupId>dom4j</groupId><artifactId>dom4j</artifactId><version>1….

  • css3选择器(一)

    css3选择器(一)直接开始正文。一、css3同级元素通用选择器【update20161228】选择器:E~F匹配任何在E元素之后的同级F元素Note:E~F选择器选中的是E元素后面同级元素中的全部F元素。例:

发表回复

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

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