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)


相关推荐

  • lasso回归matlab,机器学习Lasso回归重要论文和Matlab代码「建议收藏」

    lasso回归matlab,机器学习Lasso回归重要论文和Matlab代码「建议收藏」这是机器学习Lasso回归重要论文和Matlab代码下载,最近要做《优化理论基础》的课程大作业,需要用到mnist这个手写识别数据库,在网上查了一下如何使用,分享在这里,以飨读者。软件介绍机器学习Lasso回归重要论文和Matlab代码是纽约大学(NYU)YannLecun在上个世纪90年代做的一个关于手写数字识别的数据库。该数据库提出的Motivation是为了解决美国邮政zipcode机器…

  • 八皇后问题详解(四种解法)

    八皇后问题详解(四种解法)如果你去百度百科八皇后这个问题,你会发现人家也是历史上有头有脸的一个问题,最后一句“计算机发明后就有一万种方式解决这个问题”读起来也让程序猿们很快活。闲话少说,开始阐述我的思路:最无脑的解法一定是八个for遍历,浪费了太多的计算资源在各种无用功上面,我们稍微构思一下:首先如何决定下一个皇后能不能放这里可以有两种思路,第一种是尝试维护一个8*8的二维矩阵,每次找到一个空位放下一个皇后就把对应行列对

  • marquee标签被放弃了吗_危险废物标签如何填写

    marquee标签被放弃了吗_危险废物标签如何填写标签     标签是成对出现的标签,首标签和尾标签之间的内容就是滚动内容。     标签的属性主要有behavior、bgcolor、direction、width、height、hspace、vspace、loop、scrollamount、scrolldelay等,它们都是可选的。一.

    2022年10月25日
  • Centos7安装Postgresql 13 详细步骤(远程连接)

    Centos7安装Postgresql 13 详细步骤(远程连接)

  • linux指令_linux最常用命令

    linux指令_linux最常用命令基本命令关机:shutdown-hhaltinit0poweroff重启:shutdown-rrebootinit6pwd:查看工作目录ls:查看指定目录的内容-l:列表显示-a:显示所有,包括隐藏文件-h:人性化的显示-d:只显示目录,不查看内容cd:切换工作目录.:当前目录..:上一级目录~:用户家目录-:上次切过来的目录目录结构:linux目录…

  • Android清理设备内存具体完整演示样例(一)

    Android清理设备内存具体完整演示样例(一)

    2021年12月14日
  • 发表回复

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

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