HDOJ 5787 K-wolf Number 数位DP

数位DP的一道所谓的水题！

但是呢，必须得胆子大！

题意：求区间【L，R】中有多少个满足条件的十进制数

条件是：任意连续K个数值都不相同，K=2，3，4，5

dp最难的是设计状态和状态转移啊！

K很小，所以可以每一个有意义的数位都来一维来表示呗

dp[pos][p1][p2][p3][p4]

pos表示当前位，p4表示前一位。这里要考虑前导0的情况，p4=10的时候表示前一位为0

然后呢，最特殊的情况是：全是0的情况

转移呢，枚举即可

判断条件要根据K来说咯，如果K=2，那么当前枚举的这一位不等于p4

K=3，4，5是同理的

代码如下：

#include<bits/stdc++.h>
using namespace std;

#define LL __int64

const int maxn=25;
int K,digit[maxn];
LL dp[maxn][11][11][11][11];

bool check(int p1,int p2,int p3,int p4,int u){
    if (K==2) return u!=p4;
    else if (K==3) return u!=p4&&u!=p3;
    else if (K==4) return u!=p4&&u!=p3&&u!=p2;
    else return u!=p4&&u!=p3&&u!=p2&&u!=p1;
}

LL dfs(int pos,int p1,int p2,int p3,int p4,bool flag){
    if (pos==0) return p4!=10;
    if (flag&&dp[pos][p1][p2][p3][p4]!=-1) return dp[pos][p1][p2][p3][p4];
    LL res=0;
    int maxnum=flag?9:digit[pos];
    for(int i=0;i<=maxnum;i++){
        if (p4==10&&i==0)
            res+=dfs(pos-1,10,10,10,10,flag||i<maxnum);
        else if (check(p1,p2,p3,p4,i))
            res+=dfs(pos-1,p2,p3,p4,i,flag||i<maxnum);
    }
    if (flag) dp[pos][p1][p2][p3][p4]=res;
    return res;
}

LL calc(LL x){
    int len=0;
    while(x){
        digit[++len]=x%10;
        x/=10;
    }
    return dfs(len,10,10,10,10,0);
}

int main(){
    //freopen("input.txt","r",stdin);
    LL L,R;
    while(scanf("%I64d%I64d%d",&L,&R,&K)!=EOF){
        memset(dp,-1,sizeof(dp));
        printf("%I64d\n",calc(R)-calc(L-1));
    }
    return 0;
}

注意：

在数位dp分隔数位的时候

一定是digit【++len】而不是digit【len++】

一方面是因为最后的初始边界是len==0，就算 改成len==-1也是不行的

因为：dp的初始化会导致有问题