首页 > 代码库 > HDU_3652_数位dp

HDU_3652_数位dp

http://acm.hdu.edu.cn/showproblem.php?pid=3652

 

cal(a,b,c,d),a表示当前位置,b表示是否有13的3种状态,c表示前面的数%13后的剩余,d表示是否已无大小限制。

注意保存无大小限制的一些值,不然会超时。

 

#include<iostream>#include<cstdio>#include<cstring>using namespace std;int num[15],dp[15][3][13];int cal(int now,int sta,int pre,int ok){    if(now == 0)    return sta == 2 && pre == 0;    if(ok && dp[now][sta][pre] != -1)    return dp[now][sta][pre];    int end = ok?9:num[now],ans = 0;    for(int i = 0;i <= end;i++)    {        int staa = sta,pree = (pre*10+i)%13;        if(sta == 0 && i == 1)    staa = 1;        if(sta == 1 && i == 1)    staa = 1;        else if(sta == 1 && i == 3)    staa = 2;        else if(sta == 1 && i != 3)    staa = 0;        ans += cal(now-1,staa,pree,ok || i < end);    }    if(ok)    dp[now][sta][pre] = ans;    return ans;}int main(){    memset(dp,-1,sizeof(dp));    int n;    while(~scanf("%d",&n))    {        int counts = 0;        while(n)        {            num[++counts] = n%10;            n /= 10;        }        printf("%d\n",cal(counts,0,0,0));    }    return 0;}

 

HDU_3652_数位dp