1. 首页
2. 数位DP
3. 本页

HDU 3709 Balanced Number (数位DP)

枚举每一位为中心的情况，进行判断就可以了。

#include<iostream>
#include<cstdio>
#include<string>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
//#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double Pi = acos(-1.0);
const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const int MOD = 2520;
const int MAXN = 320000+10;

LL dp[20][20][2050];
int dig[20];

LL dfs(int len,int cen,int sum,bool mxl)
{
    if(!len)
    {
        return sum==0;
    }
    if(sum<0)
        return 0;
    if(!mxl && dp[len][cen][sum]!=-1)
    {
        return dp[len][cen][sum];
    }
    LL res=0;
    int maxlen=mxl?dig[len]:9;
    for(int i=0; i<=maxlen; ++i)
    {
        res+=dfs(len-1,cen,sum+(len-cen)*i,mxl && (i==maxlen));
    }
    if(!mxl )
    {
        dp[len][cen][sum]=res;
    }
    return res;
}

LL solve(LL x)
{
    memset(dig,0,sizeof(dig));
    int len=0;
    while(x)
    {
        dig[++len]=x%10;
        x/=10;
    }
    LL ans=0;
    for(int i=1; i<=len; ++i)
    {
        ans+=dfs(len,i,0,true);
    }
    return ans-len; //减去0 00 000 0000这种情况
}

int main()
{
    LL l,r;
    int t;
    cin>>t;
    memset(dp,-1,sizeof(dp));
    while(t--)
    {
        cin>>l>>r;
        cout<<(solve(r)-solve(l-1))<<endl;
    }

    return 0;
}