【题意】求L，R区间里面严格递增或者严格递减的数的个数。

【解题方法】数位DP。正解给了两种方法，我直接用数位DP水过去了。

【代码君】

//
//Created by just_sort 2016/10/6
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int digit[20];
LL dp[20][20][5];
LL dfs(int l,int pre,int flag,bool jud)
{
    if(l == 0) return 1;
    if(!jud && dp[l][pre][flag]!=-1) return dp[l][pre][flag];
    int nex = jud?digit[l]:9;
    LL ret = 0;
    for(int i = 0; i <= nex; i++){
        int news;
        if(flag==1&&i==0) news = 1;
        else if(flag==1||(flag==2&&pre==i)) news = 2;
        else if(flag==2) news = pre>i?3:4;
        else{
            if(flag==3&&i>pre) continue;
            if(flag==4&&i<pre) continue;
            else news = flag;
        }
        ret += dfs(l-1,i,news,jud&&(i==nex));
    }
    if(!jud) dp[l][pre][flag]=ret;
    return ret;
}
LL f(LL num)
{
    int pos = 0;
    while(num){
        digit[++pos] = num%10;
        num /= 10;
    }
    return dfs(pos,0,1,1);
}
int main()
{
    memset(dp,-1,sizeof(dp));
    int T;
    scanf("%d",&T);
    while(T--)
    {
        LL l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",f(r)-f(l-1));
    }
    return 0;
}