分析:
dp[哪一位][前一个数的倒数第二位][前一个数的倒数最后一位][0/1表示是否满足了至少有三个相邻数字的要求][0/1/2 (0:没有8和4;1:有8;2:有4)][0/1表示最高位到当前位小于或者等于R]
具体转移都在代码里了。#include#include #define MAXL 20typedef long long LL;int lmt[MAXL+10];LL dp[MAXL+10][20][20][5][5][5];int Getorg(LL num){ int ret=0; for(LL x=num;x;x/=10) ret++; memset(lmt,0,sizeof lmt); int k=0; for(LL x=num;x;x/=10,k++) lmt[ret-k]=x%10; return ret;}inline int f(int x){ if(x==8) return 1; else if(x==4) return 2; else return 0;}inline int h(int x,int y,int z){ if(x==y&&y==z) return 1; else return 0;}LL DP(LL R){ int n=Getorg(R); if(R==10000000000LL-1) return 0; memset(dp,0,sizeof dp); for(int i=1;i < R for(int p=0;p<=9;p++) dp[i][k][p][h(j,k,p)][f(p)][0]+=dp[i-1][j][k][0][0][0]; for(int p=0;p<=9;p++){ if(p==4) continue; dp[i][k][p][h(j,k,p)][1][0]+=dp[i-1][j][k][0][1][0]; } for(int p=0;p<=9;p++){ if(p==8) continue; dp[i][k][p][h(j,k,p)][2][0]+=dp[i-1][j][k][0][2][0]; } for(int p=0;p<=9;p++) dp[i][k][p][1][f(p)][0]+=dp[i-1][j][k][1][0][0]; for(int p=0;p<=9;p++){ if(p==4) continue; dp[i][k][p][1][1][0]+=dp[i-1][j][k][1][1][0]; } for(int p=0;p<=9;p++){ if(p==8) continue; dp[i][k][p][1][2][0]+=dp[i-1][j][k][1][2][0]; } // < R for(int p=0;p