HDU-5787 数位DP [2016多校]

求区间[0,N]中有多少个数满足以下条件：
任意K连续数位都是由不相同数字组成的；如数字23653(K=3)，其所有K连续数位有{236, 365, 653}，都是不存在相同数位的，既满足条件。

DP[pos][s] 表示考虑到pos数位时，以s作为最高K位的满足条件的数的个数；状态转移时只要保证新的数位与s的后K-1个数位不同即可。这里记忆化搜索的状态转移过程其实我并没有理解得很透彻，与直接递推状态的方式还是有比较大的区别，还是没有掌握到其本质。

处理s需要特别得技巧，因为需要避免将001这种数位视作合法状态，所以在最高位保留一个1，使其变成1001，这样中间重复的0就可以被检查出来；处理s的溢出位时，直接将超出K-1位的数位保留成1即可。

参考的题解：http://blog.csdn.net/ChallengerRumble/article/details/52103411

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int bit[30];
long long dp[30][20100];
int mod;
bool ok(int p, int x){
    //除最高位以外,不能有数位等于x
    while(p/10){ 
        if (p%10==x) return false;
        p /= 10;
    }
    return true;
}

long long dfs(int isTop, int pos, int notZero, int pre){
    if (pos == - 1) return 1;
    
    while(pre-mod/10 > mod/10) pre -= mod/10; 
    //这行使得pre保持前K-1的状态,并且在最高位留一个1

    if (!isTop&&dp[pos][pre] != -1) return dp[pos][pre];

    int lastBit = isTop ? bit[pos] : 9;
    long long ans = 0;
    for (int i=0;i<=lastBit;i++){
        if (!ok(pre,i)) continue;
        if (!notZero&&i==0) ans += dfs(isTop&&i==lastBit, pos-1, notZero, pre);
        else ans += dfs(isTop&&i==lastBit, pos-1, notZero+1, pre*10+i);
    }

    if (!isTop) dp[pos][pre] = ans;
    return ans;
}

long long calc(long long n){
    if (!n) return 1;
    int cnt = 0;
    while(n){
        bit[cnt++] = n%10;
        n /= 10;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(1, cnt-1, 0, 1);
}

int main(){

    long long L,R;
    int K;
    while(~scanf("%I64d%I64d%d",&L,&R,&K)){
        mod = 1;
        for (int i=0;i<K;i++) mod *= 10; 
        printf("%I64d\n", calc(R)-calc(L-1));
    }

    return 0;
}