bzoj千题计划117：bzoj1026: [SCOI2009]windy数

2021-04-26 09:26

阅读：581

标签：mst == mem php 数位dp for clu discus using

http://www.lydsy.com/JudgeOnline/problem.php?id=1026

数位DP

如果前一位填的是0，

0是前导0，下一位可以随便填

0不是前导0，下一位不能填1

为避免这种情况

枚举位数，强制不出现前导0

#include
#include
#include

using namespace std;

int dp[12][12];

int a[11];

int LEN;

int dfs(int dep,int num,bool lim)
{
    if(!lim && dp[dep][num]!=-1) return dp[dep][num];
    if(!dep) return 1;
    int up= lim ? a[dep] : 9,tmp=0; 
    for(int i=0;ii)
    {
        if(dep==LEN && !i) continue;
        if(abs(i-num)2) continue;
        tmp+=dfs(dep-1,i,lim && i==up);
    }
    if(!lim) dp[dep][num]=tmp;
    return tmp;
}

int solve(int n)
{
    if(!n) return 0;
    int len=0;
    while(n)
    {
        a[++len]=n%10;
        n/=10;
    }
    int sum=0;
    for(int i=1;ii) 
    {
        LEN=i;
        sum+=dfs(i,11,0);
    }
    LEN=len; 
    sum+=dfs(len,11,1);
    return sum;
}

int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    memset(dp,-1,sizeof(dp));
    printf("%d\n",solve(b)-solve(a-1));
}

1026: [SCOI2009]windy数

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 8771 Solved: 3959
[Submit][Status][Discuss]

Description

　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，
在A和B之间，包括A和B，总共有多少个windy数？

Input

　　包含两个整数，A B。

Output

　　一个整数

Sample Input

【输入样例一】
1 10
【输入样例二】
25 50

Sample Output

【输出样例一】
9
【输出样例二】
20

HINT

【数据规模和约定】

100%的数据，满足 1

bzoj千题计划117：bzoj1026: [SCOI2009]windy数

标签：mst == mem php 数位dp for clu discus using

原文地址：http://www.cnblogs.com/TheRoadToTheGold/p/7898217.html

上一篇：常用JSR-303数据校验

下一篇：C#常用类操作

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj千题计划117：bzoj1026: [SCOI2009]windy数
文章链接：http://soscw.com/essay/79743.html

亲，登录后才可以留言！

bzoj千题计划117：bzoj1026: [SCOI2009]windy数

1026: [SCOI2009]windy数

Description

Input

Output

Sample Input

Sample Output

HINT

评论

热门文章

推荐文章

最新文章

置顶文章