首页 > 代码库 > uestc 250 windy数 【数位dp】
uestc 250 windy数 【数位dp】
题目:uestc 250 windy数
题意:
windy定义了一种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 <cstdio> #include <cstring> #include <vector> #include <algorithm> #include <map> #include <string> #include <iostream> #include <cmath> 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<=9;i++) dp[1][i]=1; for(int i=2;i<N;i++) { for(int j=0;j<=9;j++) { for(int k= 0;k<=9;k++) if(abs(j-k)>=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;i<cnt;i++) //先把长度为1至cnt-1计入 for(int j=1;j<10;j++) ans+=dp[i][j]; for(int j=1;j<digit[cnt];j++) //确定最高位 ans+=dp[cnt][j]; for(int i=cnt-1;i>0;i--){ for(int j=0;j<digit[i];j++) if(abs(j-digit[i+1])>=2) ans+=dp[i][j]; if(abs(digit[i]-digit[i+1])<2) //如果高位已经出现非法,直接退出 break; } return ans; } int main() { isit(); int x,y; while(~scanf("%d%d",&x,&y)) { printf("%d\n",solve(y+1)-solve(x)); } return 0; }
uestc 250 windy数 【数位dp】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。