【zoj3962】Seven Segment Display(數位dp)

記錄一個菜逼的成長。。

題目連結

題目大意:

T組資料。

給你一個n，和8位的十六進制數num，每一位的十六進制數都有一個權值，

問[num,num+n-1]的每個數的權值和。

省賽的時候，後面想到了數位dp，但是在想狀态的時候，卡在了第二維的定義上。

(其實當時我很想睡覺。orz.還有就是我太菜。

(貌似權值和作為dp的狀态很常見，以後注意一下。。這麼水的題，我tm竟然現場沒想到,菜的想撞牆。

dp[i][j]:=表示數位枚舉到第i位，和為j的總價值。

那麼接下來就簡單了，直接套數位dp的模闆，胡亂搞一搞。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int num[] = {,,,,,,,,,,,,,,,},bit[];
LL dp[][];
LL dfs(int pos,int sum,int limit)
{
    if(pos == -)return sum;
    if(!limit && dp[pos][sum] != -)return dp[pos][sum];
    int ed = (limit ? bit[pos] : );
    LL ret = ;
    for( int i = ; i <= ed; i++ ){
        ret += dfs(pos-,sum + num[i],limit && i == ed);
    }
    if(!limit)dp[pos][sum] = ret;
    return ret;
}
LL solve(LL x)
{
    for( int i = ; i < ; i++ ){
        bit[i] = x % ;
        x /= ;
    }
    return  dfs(,,);
}
int main()
{
    memset(dp,-,sizeof(dp));
    int T;scanf("%d",&T);
    while(T--){
        int n;
        LL num;
        scanf("%d%llX",&n,&num);
        if(num+n- <= (LL)){
            printf("%lld\n",solve(num+n-) - solve(num-));
        }
        else {
            LL x = num + n - ;
            x %= (LL);
            printf("%lld\n",solve((LL)) - solve(num-) + solve(x));
        }
    }
    return ;
}