hdu 5787 K-wolf Number 2016 Multi-University Training Contest 5 1007 (不允许前导0的数位dp)

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月02日 星期二 16时28分29秒
 4File Name :code/multi2016/#5/1007.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31LL l,r;
32int k;
33LL digit[25];
34LL dp[22][11][11][11][11];
35int LEN;
36LL dfs(int pos,int k1,int k2,int k3,int k4,bool limit,bool prehasnonzero)
37{
38    if (pos==0) return 1;
39    if (prehasnonzero&&!limit&&dp[pos][k1][k2][k3][k4]!=-1LL) return dp[pos][k1][k2][k3][k4];

 1    int mx = limit?digit[pos]:9;
 2    LL res = 0LL;
 3    if (!prehasnonzero)
 4    {
 5	for  (int i = 0 ; i <= mx ;i++)
 6	{
 7	    res +=dfs(pos-1,i,10,10,10,limit&&i==mx,i==0?false:true);
 8	}
 9    }
10    else
11    {
12	for ( int i = 0 ; i <= mx ; i++)
13	{
14	   // if (i==k1||i==k2||i==k3||i==k4) continue;
15	    if (k>=2&&i==k1) continue;
16	    if (k>=3&&i==k2) continue;
17	    if (k>=4&&i==k3) continue;
18	    if (k>=5&&i==k4) continue;

1	    res +=dfs(pos-1,i,k1,k2,k3,limit&&i==mx,true);
2	}
3    }

 1    if (prehasnonzero&&!limit) dp[pos][k1][k2][k3][k4] = res;
 2    return res;
 3}
 4LL solve ( LL n)
 5{
 6    ms(digit,0);
 7    int len = 0 ;
 8    while (n)
 9    {
10	digit[++len] = n;
11	n/=10;
12    }
13    LEN = len;
14    return dfs(len,10,10,10,10,true,false);
15}
16int main()
17{
18	#ifndef  ONLINE_JUDGE 
19	freopen("code/in.txt","r",stdin);
20  #endif
21	while (~scanf("%lld%lld%d",&l,&r,&k))
22	{
23	    ms(dp,-1);
24//	    cout<<"solve(100):"<<solve(100)<<endl;
25//	    cout<<"solve(r):"<<solve(r)<<" solve(l-1):"<<solve(l-1)<<endl;
26	    LL ans = solve(r)-solve(l-1);
27	    printf("%lld\n",ans);
28	}
29  #ifndef ONLINE_JUDGE  
30  fclose(stdin);
31  #endif
32    return 0;
33}