HDU 3652 B-number(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3652

题意:类似3555,0-n之间某个数中包含13,且整个数能被13整除 分析:数位DP          同余定理。比如1234对于m取余,相当于123的余数+4在对n取余

#include<stdio.h>
#include<string.h>
#define LL long long
const int MN=100;
LL dp[MN][20][10];//位置,余数,状态,刚开始余数那里数组开小了
int digit[MN];

LL DFS(int pos,int mod,int have,int doing)
{
    if(pos==-1) return ((have==2) && (mod==0));
    if(!doing && dp[pos][mod][have]!=-1) return dp[pos][mod][have];
    int end=doing?digit[pos]:9;
    LL ans=0;
    for(int i=0;i<=end;i++)
    {
        int MOD=(mod*10+i)%13;
        int nhave=have;
        if(have==0 && i==1)
           nhave=1;
        if(have==1 && i==3)
           nhave=2;
        if(have==1 && i!=3)
           nhave=0;
        if(have==1 && i==1)
           nhave=1;
        ans+=DFS(pos-1,MOD,nhave,(doing && i==end));
    }
    if(!doing)
    {
        dp[pos][mod][have]=ans;
    }
    return ans;
}

LL cal(LL n)
{
    int len=0;
    while(n)
    {
        digit[len++]=n%10;
        n/=10;
    }
    memset(dp,-1,sizeof(dp));
    return DFS(len-1,0,0,1);
}

int main()
{
    int i,j;
    LL n;
    while(scanf("%I64d",&n)!=EOF)
    {
        printf("%I64d\n",cal(n));
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏kalifaの日々

C++迪杰斯特拉最短路径算法实现

input 第一行表示这个图有4条边,下面五行代表这个图的5条边。 4 0 2 2 0 1 5 1 3 2 2 3 6 -1 0 0 ? 输入样例 out 分别...

35640
来自专栏机器学习实践二三事

ResNet && DenseNet(实践篇)

上篇博客说了ResNet和DenseNet的原理,这次说说具体实现 ResNet def basic_block(input, in_features, out...

26480
来自专栏机器学习与自然语言处理

Lake Counting(POJ-2386)

题目链接: http://poj.org/problem?id=2386 题目大意: 计算出相连的'W'有多少块 所需算法: 深度优先搜索(DFS) 主要思路:...

25470
来自专栏zaking's

用js来实现那些数据结构15(图01)

21040
来自专栏编程理解

数据结构(八):邻接表与邻接矩阵

邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

25830
来自专栏python读书笔记

《python算法教程》Day5 - DFS遍历图(邻接字典)DFS简介代码示例

这是《python算法教程》的第5篇读书笔记。这篇笔记的主要内容为运用DFS(深度优先搜索,depth first search)对图(邻接字典)进行遍历。 D...

666110
来自专栏从流域到海域

图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。 /*Graph存储结构*/ //邻接矩阵表示法 #define MAX_VERTEX...

39660
来自专栏架构之路

Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

一、背景介绍 强连通分量是有向图中的一个子图,在该子图中,所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象,因为它满足 自反性:顶点V...

42760
来自专栏向治洪

数据结构之图

基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间...

22650
来自专栏nnngu

数据结构10 图

这一篇我们要总结的是图(Graph),图可能比我们之前学习的线性结构和树形结构都要复杂,不过没关系,我们一点一点地来总结。那么关于图,我将从以下几点进行总结: ...

36570

扫码关注云+社区

领取腾讯云代金券