定义windy数：相邻数字的差至少是2的数，例如10不是windy数，而13是windy数。求给定区间中有多少windy数。区间端点范围为 [1, 2000000000]
dfs写法
#include <stdio.h> #include <string.h> #define N 10 int dp[N][N],digit[N]; int dfs(int pos,int last,int z,int f) { if(pos==-1) return 1; if(z&&!f&&dp[pos][last]!=-1) return dp[pos][last]; int max=f?digit[pos]:9; int ret=0; if(z==0) { for(int i=0;i<=max;i++) { ret+=dfs(pos-1,i,i,f&&i==max); } } else { for(int i=0;i<=max;i++) { if((i-last)*(i-last)<4) continue; ret+=dfs(pos-1,i,1,f&&i==max); } } if(z&&!f) dp[pos][last]=ret; return ret; } int cal(int x) { int pos=0; while(x) { digit[pos++]=x%10; x/=10; } return dfs(pos-1,0,0,1); } int main() { memset(dp,-1,sizeof(dp)); int a,b; while(~scanf("%d%d",&a,&b)) printf("%d\n",cal(b)-cal(a-1)); return 0; }
递推写法
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define LEN 15 char a[LEN],b[LEN]; int n,m; int dp[LEN][10][2][2][2]; //第二维记录最后的数字，第三维记录状态是否合法，第四维记录该位是否是最高位，最后一维记录是否达到上界 int nextstate(int cur,int last,int in) { if(cur==0 && abs(last-in)>=2) return 0; return 1; } int nextflag1(int cur,int in,int max) { if(cur==1 && in==max) return 1; if(cur==1 && in>max) return -1; return 0; } int nextflag2(int cur,int in) { if(cur==1 && in==0) return 1; return 0; } int DP(char *s,int len) { memset(dp,0,sizeof(dp)); dp[0][0][0][1][1]=1; for(int i=1;i<=len;i++) for(int last=9;last>=0;last--) for(int state=0;state<2;state++) for(int flag1=0;flag1<2;flag1++) for(int flag2=0;flag2<2;flag2++) for(int in=0;in<10;in++) { int nxt=nextstate(state,last,in); if(flag2==1) nxt=0; if(nextflag1(flag1,in,s[i]-'0')!=-1) dp[i][in][nxt][nextflag1(flag1,in,s[i]-'0')][nextflag2(flag2,in)]+=dp[i-1][last][state][flag1][flag2]; } int ret=0; for(int i=0;i<10;i++) ret+=dp[len][i][0][0][0]+dp[len][i][0][1][0]; return ret; } int main() { while(~scanf("%d%d",&n,&m)) { n--; sprintf(a+1,"%d",n); sprintf(b+1,"%d",m); printf("%d\n",DP(b,strlen(b+1))-DP(a,strlen(a+1))); } return 0; }