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

题意:给出l,r,k求区间[l,r]中满足任意相邻k个数字都不相同的数的个数.

思路:数位dp,dp[i][k1][k2][k3][k4]表示长度为i,前1位是k1,前2位是k2,前3位是k3,前4位是k4的方案数. 注意不允许前导0.2A

 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];
40
41    int mx = limit?digit[pos]:9;
42    LL res = 0LL;
43    if (!prehasnonzero)
44    {
45	for  (int i = 0 ; i <= mx ;i++)
46	{
47	    res +=dfs(pos-1,i,10,10,10,limit&&i==mx,i==0?false:true);
48	}
49    }
50    else
51    {
52	for ( int i = 0 ; i <= mx ; i++)
53	{
54	   // if (i==k1||i==k2||i==k3||i==k4) continue;
55	    if (k>=2&&i==k1) continue;
56	    if (k>=3&&i==k2) continue;
57	    if (k>=4&&i==k3) continue;
58	    if (k>=5&&i==k4) continue;
59
60	    res +=dfs(pos-1,i,k1,k2,k3,limit&&i==mx,true);
61	}
62    }
63
64    if (prehasnonzero&&!limit) dp[pos][k1][k2][k3][k4] = res;
65    return res;
66}
67LL solve ( LL n)
68{
69    ms(digit,0);
70    int len = 0 ;
71    while (n)
72    {
73	digit[++len] = n;
74	n/=10;
75    }
76    LEN = len;
77    return dfs(len,10,10,10,10,true,false);
78}
79int main()
80{
81	#ifndef  ONLINE_JUDGE
82	freopen("code/in.txt","r",stdin);
83  #endif
84	while (~scanf("%lld%lld%d",&l,&r,&k))
85	{
86	    ms(dp,-1);
87//	    cout<<"solve(100):"<<solve(100)<<endl;
88//	    cout<<"solve(r):"<<solve(r)<<" solve(l-1):"<<solve(l-1)<<endl;
89	    LL ans = solve(r)-solve(l-1);
90	    printf("%lld\n",ans);
91	}
92  #ifndef ONLINE_JUDGE
93  fclose(stdin);
94  #endif
95    return 0;
96}

相关文章