1026: [SCOI2009]windy数

2019-11-06 07:18:17

字体：大中小

来源：转载

供稿：网友

题目链接

题目大意：不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。求[l,r]中的windy数

题解：数位dp

#include <iostream>#include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int M=12;int l,r;int f[M][M]; int bit[M];inline int ass(int x){return x>0?x:-x;}int dfs(int x,int s,bool z,bool e){ if(x==0) return 1; if(!z&&!e&&f[x][s]!=-1) return f[x][s]; int ans=0; int u=e?bit[x]:9; for(int i=0;i<=u;i++){ if(!z&&ass(i-s)<2) continue; ans+=dfs(x-1,i,z&&!i,e&&(i==u)); } return !z&&!e?f[x][s]=ans:ans;}int solve(int x){ int len=0; while(x) bit[++len]=x%10,x/=10; return dfs(len,0,1,1);}void work(){ PRintf("%d/n",solve(r)-solve(l-1));}void init(){ memset(f,-1,sizeof(f)); cin>>l>>r;}int main() { init(); work(); return 0;}

上一篇：【数据结构】交换排序

下一篇：421. Maximum XOR of Two Numbers in an Array