首页 > 代码库 > uestc250windy数数位dp

uestc250windy数数位dp

#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;int dp[100][100][2];int up[1000];int ab(int x){    return x>0? x:-x;}int dfs(int pos,int top,int first,int flag){    if(pos<=0) return first==1;    if(first&&!flag&&~dp[pos][top][first]) return dp[pos][top][first];    int limit = flag? up[pos]: 9,ret=0;    for(int i= 0;i<=limit;i++){         int t= ab(top-i);          if(t>=2||!first) ret+=dfs(pos-1,i,first||i,flag&&(i==limit)); //这个判断是海哥告诉的,非常吊,自己品味。    }    return  flag? ret: dp[pos][top][first] = ret;}int solve(int x){    int len=0;    while(x){        up[++len]=x%10;        x/=10;    }    return dfs(len,100,0,1);}int main(){    memset(dp,-1,sizeof(dp));    int n,m;    while(scanf("%d%d",&n,&m)!=EOF){        cout<<solve(m) - solve(n-1) <<endl;    }    return 0;}