CSU 1993: 大司馬的三角形中單（數位DP）

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

LL dp[20][5][10][2][2];
int bit[20];

LL DFS(int pos,int can,int endbit,bool isok,bool prezero,bool limit){
  
  if(pos==-1) return ((can==2 || can==3) && isok);
  if(!limit && dp[pos][can][endbit][isok][prezero]!=-1) return dp[pos][can][endbit][isok][prezero];
  int end=limit?bit[pos]:9;
  LL ans=0;
  for(int i=0;i<=end;i++){
    
    int newcan=can;
    bool newisok=isok;
    if(prezero) newcan=0,newisok=true;
    else if((can==0 || can==1) && i>endbit) newcan=1,newisok=(isok && true);
    else if((can==1 || can==2) && i<endbit) newcan=2,newisok=(isok && true);
    else if((can==2 || can==3) && endbit==0 && i==0) newcan=3,newisok=(isok && true);
    else newisok=false;
    ans+=DFS(pos-1,newcan,i,newisok,prezero && i==0,limit && i==end);
  }
  return limit?ans:dp[pos][can][endbit][isok][prezero]=ans;
}

LL slove(LL num){
  
  int pos=0;
  while(num){
    
    bit[pos++]=num%10;
    num/=10;
  }
  return DFS(pos-1,0,0,true,true,true);
}

int main(){
  
  int T;
  scanf("%d",&T);
  memset(dp,-1,sizeof(dp));
  while(T--){
    
    LL l,r;
    scanf("%lld%lld",&l,&r);
    printf("%lld\n",slove(r)-slove(l-1));
  }
}