Codeforces 205 C. Little Elephant and Interval(디지털 dp)

링크: C. Little Elephant and Interval 제목: r 구간에서 처음과 끝이 같은 수의 개수를 구합니다.사고방식: 무모한 디지털 dp를 썼는데 다른 교묘한 방법이 있는 것 같다. 여기는 첫 번째 0이 아닌 수를 수위로 하고 마지막에 마지막 사람과 첫 번째 사람이 같은지 아닌지를 판단하며 이 수는 0이 될 수 없다.코드:

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll ;
const int maxn=1e6+7;
ll dp[20][20][3],a[20],poss;
ll dfs(int pos,int fir,int pre,int limit,int sta){
    if(pos==-1) return fir == pre &&sta == 0;

    if(!limit&&fir!=-1&&dp[pos][fir][sta]!=-1) return dp[pos][fir][sta];

    int up=limit ? a[pos] : 9;
    ll tmp=0;
    for(int i=0; i <= up; i++){
        if(sta && i != 0) fir = i;
        tmp += dfs(pos-1,fir,i,limit &&(i == a[pos]),sta && i == 0);
    }
    if(!limit&&fir!=-1) dp[pos][fir][sta]=tmp;
    return tmp;
}
ll solve(ll x){
     int pos=0;
     while(x>0){
         a[pos++]=x%10;
         x/=10;
     }
     poss = pos - 1;
     return dfs(pos-1,-1,-1,1,1);
}
int main(){
    memset(dp,-1,sizeof(dp));
    ll a,b;
    cin>>a>>b;
    cout<<solve(b) -solve(a-1) <<endl;
}