uestc 250 windy数【数位dp】

2020-12-13 14:01

阅读：362

标签：c++ algorithm 二进制 dp 数位dp

题目：uestc 250 windy数

题意：

windy定义了一种windy数。

不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。

分析：首先定义dp【i】【j】：有 i 位最高位为 j 的出现次数。

首先通过暴力预处理出dp值来。

很明显其满足区间减法，通过求0---x的值通过区间减法求x---y 的。

那么假如我们要求0---257的，

首先求0---99，直接遍历0---9的然后10--90的依次求出。

然后求100--200的，直接遍历100--200求和即可

最后求200--257的，我们依次求2和相邻的5之间差值超过2的，求和，然后5和相邻7之间差值超过2的，加油相邻小于2的，直接不满足跳出

AC代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define Del(a,b) memset(a,b,sizeof(a))
typedef long long LL;
const double esp = 1e-10;
const long long N = 15;
int dp[N][10];  //最高位
void isit()
{
    memset(dp,0,sizeof(dp));
    for(int i=0;i=2)
                dp[i][j]+=dp[i-1][k];
        }
    }
    //printf("%d\n",dp[3][1]);
}
int solve(int x){
    int digit[20],cnt=0;
    while(x){
        digit[++cnt]=x%10;
        x/=10;
    }
    int ans=0;
    for(int i=1;i0;i--){
        for(int j=0;j=2)
                ans+=dp[i][j];
        if(abs(digit[i]-digit[i+1])

uestc 250 windy数 【数位dp】
标签：c++   algorithm   二进制   dp   数位dp   
原文地址：http://blog.csdn.net/y990041769/article/details/40544419

上一篇：使用Autofac在ASP.NET Web API上实现依赖注入

下一篇：C# - as

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：uestc 250 windy数【数位dp】
文章链接：http://soscw.com/essay/33632.html

亲，登录后才可以留言！

uestc 250 windy数【数位dp】

评论

热门文章

推荐文章

最新文章

置顶文章

uestc 250 windy数 【数位dp】

评论

热门文章

推荐文章

最新文章

置顶文章

uestc 250 windy数【数位dp】