[SCOI2009]windy数

2021-06-16 02:04

阅读：647

标签：scanf long bad sam typedef 数位 bit for 限制

windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，

在A和B之间，包括A和B，总共有多少个windy数？

输入输出格式

输入格式：

包含两个整数，A B。

输出格式：

一个整数

输入输出样例

输入样例#1：复制

1 10

输出样例#1：复制

输入样例#2：复制

25 50

输出样例#2：复制

说明

100%的数据，满足 1

dp[i][j]：表示共有i位，其中最高位为j满足条件的方案数。

其中定义j=10为前导零不受限制。

则按照数位dp板子。

分3种情况。

第一种情况：当前位-上一位大于等于2 比如 47xxxxx，则需要从0，累加到2，再从6累加到6.

第二种情况，上一位比当前为大等于2 比如74xxxxx 则从0循环到4-1

第三种情况 abs(上一位-当前位）小于2 如 45

则从0循环到4-2，然后直接break掉。因为5的时候不满足条件。

#include 
using namespace std;
typedef long long ll;
ll dp[15][15];
void init()
{
    for(int i=0;i=0;--k)
                {
                    dp[i][j]+=dp[i-1][k];
                }
            }
            else
            {
                for(int k=1;k0)
    {
        a[++cnt]=x%10;
        x/=10;
    }
    ll res=0;
    for(ll i=a[cnt]-1;i>=1;--i)
    {
        res+=dp[cnt][i];
    }
    res+=dp[cnt][10];
    for(int i=cnt-1;i>=1;--i)
    {
        if(abs(a[i+1]-a[i])=2)
        {
            for(ll j=a[i]-1;j>=a[i+1]+2;j--)
            {
                res+=dp[i][j];
            }
            for(int j=0;j=2)
        {
            for(ll j=a[i]-1;j>=0;--j)
            {
                res+=dp[i][j];
            }
        }
    }
    return res;
}
int main()
{
    init();
    ll x,y;
    //cout

[SCOI2009]windy数

标签：scanf long bad sam typedef 数位 bit for 限制

原文地址：https://www.cnblogs.com/zyf3855923/p/10353675.html

上一篇：Windows Server 2016-客户端加域准备工作

下一篇：C#操作INI文件之Vini.cs的使用

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

亲，登录后才可以留言！

[SCOI2009]windy数

输入输出格式

输入输出样例

说明

评论

热门文章

推荐文章

最新文章

置顶文章