BZOJ1026: [SCOI2009]windy数(数位dp)

题意

题目链接

Sol

很zz的数位dp

$f[i][j]$表示第$i$位,前一位是$j$的方案数

转移的时候枚举一下是否相同即可

注意当lim达到上界的时候是不能记忆化的!

/*
 
*/
#include<cstdio>
#include<map>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
const int MAXN = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int A, B;
int num[MAXN], tot = 0, f[21][11];
int dfs(int x, bool lim, int pre) {
    if(x == 0) return pre != -1;
    if(!lim && f[x][pre]) return f[x][pre];
    int ans = 0;
    for(int i = 0; i <= (lim ? num[x] : 9); i++) {
        if(i == 0 && pre == -1) ans += dfs(x - 1, lim && i == num[x], -1);
        else if(abs(pre - i)>= 2) ans += dfs(x - 1, lim && i == num[x], i);
    }
    if(!lim) f[x][pre] = ans;
    return ans;
}
int solve(int x) {
    tot = 0;
    while(x) num[++tot] = x % 10, x /= 10;
    return dfs(tot, 1, -1);
}
 main() {
    A = read(); B = read();
    printf("%lld", solve(B) - solve(A - 1));
    return 0;
}
/*
25 50
*/

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

扒一扒基于词法分析和语法分析的SQL注入攻击检测

周末了,又到了一星期中的美好时刻,因为期待,因为渲染在时光中的慵散。本周,Black Hat大会,应该是安全界中的大事件。 这不,经过一番紧锣密鼓的搜罗,发现了...

5528
来自专栏思考的代码世界

Python网络数据采集之数据清洗|第06天

1373
来自专栏技术点滴

Lisp的本质(The Nature of Lisp)学习思考

Lisp的本质(The Nature of Lisp)学习思考 作者 Slava Akhmechet 译者 Alec Jang 出处: http://www....

2455
来自专栏精讲JAVA

Gof设计模式之静态工厂模式(五)

设计模式之静态工厂模式 01前言 该系列模式已经更新五篇,希望大家可以多看看以前的模式,并且从今天开始我打算换一种讲解方式,我不在贴出运行结果...

2026
来自专栏HansBug's Lab

算法模板——Dinic网络最大流 1

实现功能:同sap网络最大流 今天第一次学Dinic,感觉最大的特点就是——相当的白话,相当的容易懂,而且丝毫不影响复杂度,顶多也就是代码长个几行 主要原理就是...

3048
来自专栏张善友的专栏

微软在动态语言支持上超越了Java?

当.NET在2000/2001年第一次发布的时候,Java社区认为它仅仅是从语言以及标准库上对Java的一个“克隆”。我们把二者的简单实例代码进行比较以后就可以...

18310
来自专栏数据结构与算法

P1629 邮递员送信

题目描述 有一个邮递员要送东西,邮局在节点1.他总共要送N-1样东西,其目的地分别是2~N。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有M条道路,...

2877
来自专栏iOS开发日记

给我十个可爱的订阅的粉丝带来的一篇iOS面经。。。。

大大小小参加过不下30+公司的面试,其中不乏BAT、TMD等一线互联网公司,总结一下,发现大厂招聘都有一个共性。

47813
来自专栏炉边夜话

调查问卷:测试你对多核多线程的认知程度

        目前,多核多线程编程已经成为一种趋势,但大部分程序员还没有从串行程序的思维中走出来。即使有些人对多核多线程的概念有所了解,但也是一知半解,...

1322
来自专栏圣杰的专栏

DDD理论学习系列(11)-- 工厂

1.引言 在针对大型的复杂领域进行建模时,聚合、实体和值对象之间的依赖关系可能会变得十分复杂。在某个对象中为了确保其依赖对象的有效实例被创建,需要深入了解对象实...

25610

扫码关注云+社区

领取腾讯云代金券