传送门

md直接wa了78次，身败名裂

没学过数位DP硬搞了一道数位DP的模板题，感觉非常的愉（sha）悦（cha）。

二分转化枚举思想。首先DP预处理出来$f[i][j]$表示有$i$位且第$i$位为$j$的windy数有多少个，然后搞个$g[i]$表示$i$位上可以有多少个windy数。然后二分出来最大的小于$A$和$B$的windy数。相减就好了。

//BZOJ 1026//by Cydiater//2016.10.24#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <ctime>#include <cstring>#include <string>#include <algorithm>#include <queue>#include <map>#include <iomanip>#include <bitset>using namespace std;#define ll long long#define up(i,j,n)       for(int i=j;i<=n;i++)#define down(i,j,n)     for(int i=j;i>=n;i--)const int oo=0x3f3f3f3f;inline ll read(){    char ch=getchar();ll x=0,f=1;    while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}    return x*f;}ll f[15][15],A,B,g[15],ten[15];namespace solution{    void init(){        A=read();B=read();        ll tmp=1;        up(i,1,14){            ten[i]=tmp;            tmp*=10LL;        }    }    ll col(ll pos,ll re,ll last){        if(pos==0)return 0;        if(last==-1){			if(pos==1){				if(re<=f[pos][0])return 0;				re-=f[pos][0];			}            up(i,1,9){                if(re<=f[pos][i])return  ten[pos]*i+col(pos-1,re,i);                re-=f[pos][i];            }        }else{			if(pos==1&&last-2>=0){				if(re<=f[pos][0])return 0;				re-=f[pos][0];			}            if(last-2>=0){                ll sum=0;                up(i,2,9)sum+=f[pos-1][i];                if(re<=sum)      return col(pos-1,re,0);                else            re-=sum;            }            up(i,1,9)if(abs(i-last)>=2){                if(re<=f[pos][i])    return ten[pos]*i+col(pos-1,re,i);                re-=f[pos][i];            }        }    }    ll check(ll id){        ll last=-1,ans=0,high=0;        down(i,11,1)if(g[i]<id){            high=i;            id-=g[i];            break;        }        ans=col(high+1,id,-1);        return ans;    }    ll get(ll num){        ll leftt=0,rightt=10000000000LL,mid;        while(leftt+1<rightt){            mid=(leftt+rightt)>>1;            if(check(mid)<=num)   leftt=mid;            else                rightt=mid;        }        if(check(rightt)<=num)       return rightt;        return leftt;    }    void slove(){        memset(f,0,sizeof(f));        up(i,0,9)f[1][i]=1;        up(i,2,14)up(j,0,9){            up(k,j+2,9)f[i][j]+=f[i-1][k];            down(k,j-2,0)f[i][j]+=f[i-1][k];        }		if(A>B)swap(A,B);        memset(g,0,sizeof(g));        g[0]=1;        up(i,1,14){            g[i]+=g[i-1];            up(j,1,9)g[i]+=f[i][j];        }        cout<<get(B)-get(A-1)<<endl;    }}int main(){	//freopen("input.in","r",stdin);	//freopen("out1.out","w",stdout);    using namespace solution;    init();    slove();    return 0;}

BZOJ1026: [SCOI2009]windy数