hdu 4722 Good Numbers（找規律，記憶化搜尋，數位dp）

題目連結：

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

解題思路：

題目大意：

給你兩個數a,b（a<=b）,問你a~b滿足各個數位相加能整除10的個數，含邊界。

算法思想：

先枚舉一下0~200内滿足條件的值，0，19，28，37，46，55，64，73，82，91，109，118，127，136，145，154，163，172，181，190.規律很顯然就出來了，0~10中有一個，10~20中有一個。。。可知：每十個中必有一個（自己可以在紙上畫一下）。一個很大的數共有n位，前面n-1位的和是p而最後一位還沒确定，最後一位可以取q=0~9，自己可以想一下結果肯定是(p+q)%10,而模上10以後的結果必是從0~9，是以每十個裡面必有一個。接下來的就好辦了，問你a~b滿足條件的個數，就先求出邊界c~d(c<=a且最大的滿足條件的數,d<=b且最大的滿足條件的數)，最後結果就是（d-c）/10。

AC代碼（找規律）；

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

bool judge(ll x){
    int sum = 0;
    while(x){
        sum += x%10;
        x /= 10;
    }
    if(sum % 10 == 0)
        return true;
    else
        return false;
}

int main(){
    int T,t = 1;
    scanf("%d",&T);
    while(T--){
        ll a,b;
        scanf("%lld%lld",&a,&b);
        a--;
        while(!judge(a))
            a--;
        while(!judge(b))
            b--;
        printf("Case #%d: %lld\n",t++,b/10-a/10);
    }
    return 0;
}
           

AC代碼（記憶化搜尋）：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
const int maxn = 25;

ll dp[maxn][12];
ll digit[maxn];
ll a,b;

ll dfs(int pos,int pre,bool limit){//pre表示前面各位數字之和對該數取模的結果 
    if(pos == -1)
        return pre == 0;
    if(!limit && dp[pos][pre]!=-1)
        return dp[pos][pre];

    ll res = 0,tmp = limit?digit[pos]:9;

    for(int i = 0; i <= tmp; i++){
        int new_pre = (pre+i)%10;
        res += dfs(pos-1,new_pre,limit&&i==tmp);
    }
    if(!limit)
        dp[pos][pre] = res;
     return res;
}

ll solve(ll n)
{
     int len=0;
     while(n){
         digit[len++] = n%10;
         n /= 10;
     }
     return dfs(len-1,0,true);
}

int main(){
     int T;
     scanf("%d",&T);
     for(int i = 1; i <= T; i++){
         memset(dp,-1,sizeof(dp));
         scanf("%lld%lld",&a,&b);
         printf("Case #%d: %lld\n",i,solve(b)-solve(a-1));
     }
     return 0;
}
           

dp[i][j]表示到第i位，數字和%10為j，然後進行dp，注意完全比對的情況是要+1，而其他情況是從0 到 9 都要考慮

AC代碼（數位dp）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
ll a,b,dp[20][10];
ll v[20],vn;

void solve2(ll num){
    vn = 0;
    while(num){
        v[++vn] = num % 10;
        num /= 10;
    }
    for(int i = 1; i <= vn / 2; i++)
        swap(v[i], v[vn - i + 1]);
}

ll solve(ll num){
    if (num == -1)
    return 0;
    memset(dp, 0, sizeof(dp));
    solve2(num);
    int x = 0;
    for (int i = 1; i <= vn; i++){
        for (int j = 0; j < 10; j++){
            for (int k = 0; k < 10; k++){
                dp[i][(j + k) % 10] += dp[i - 1][j];
            }
        }
        for (int j = 0; j < v[i]; j++) {
            dp[i][(x + j) % 10]++;
        }
        x = (x + v[i]) % 10;
    }
    if (!x)
        dp[vn][0]++;
    return
        dp[vn][0];
}

int main(){
    int T,t = 1;
    scanf("%d", &T);
    while(T--){
        scanf("%lld%lld",&a,&b);
        printf("Case #%d: %lld\n",t++,solve(b)-solve(a-1));
    }
    return 0;
}