SGU 390-Tickets(디지털 dp)

제목: l-r라는 표가 있는데 행인에게 보내야 한다. 주어진 표의 번호의 각 숫자의 총계(한 사람이 표가 여러 장 있을 수 있음)가 적지 않을 때 k를 보내기 시작한다. 몇 명을 보낼 수 있는지 구한다.
분석: 이 문제는 생각하기 어려워요. 문제풀이를 참고해 봤어요. dp[i][sum][left] 길이 i 현재 디지털과sum 앞 트리의 남은 합
 

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  1000000007;

ll l,r;

int k,lbit[20],rbit[20],used[20][210][1010];

struct node{

    ll num,left;//num     、left       

    node(ll num = 0, ll left = 0) : num(num), left(left) {}

    node operator += (node b)

    {

        num += b.num;

        left = b.left;

        return *this;

    }

}dp[20][210][1010];

node dfs(int i,int sum,int left,int le,int re){

    if(i==0){

        if(sum+left>=k)

        return node(1,0);

        return node(0,sum+left);

    }

    if(used[i][sum][left]&&!le&&!re)

        return dp[i][sum][left];

    int ll=le?lbit[i]:0;

    int rr=re?rbit[i]:9;

    node a(0,left);

    for(int v=ll;v<=rr;++v){

        a+=dfs(i-1,sum+v,a.left,le&&(v==ll),re&&(v==rr));

    }

    if(!le&&!re){

        dp[i][sum][left]=a;

        used[i][sum][left]=1;

    }

    return a;

}

void solve(){

    memset(used,0,sizeof(used));

    memset(dp,0,sizeof(dp));

    int len=0;

    while(r){

        rbit[++len]=r%10;

        r/=10;

        lbit[len]=l%10;

        l/=10;

    }

    node t=dfs(len,0,0,1,1);

    printf("%I64d
",t.num);

}

int main()

{

    scanf("%I64d%I64d%d",&l,&r,&k);

        solve();

return 0;

}