題目鏈接
題目大意：不含前導零且相鄰兩個數字之差至少為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(){新聞熱點
疑難解答
