hdu3709——数位dp+枚举

题目链接：https://vjudge.net/problem/HDU-3709

题目大意：求区间[l,r]里面满足平衡数的数的个数

平衡数定义：可以通过找一个平衡数位，该数位左边的数位乘以偏移距离的和等于右边的数位乘以偏移距离的和。

e.g:4139，平衡数位为3,4*2+1=9,因此该数是平衡数。

题解：

定义状态dp[pos][k][sum]表示枚举到pos位置，当前平衡数位位置为k，前面数位的数位乘以偏移距离的和。

最后判断一下是否等于0就行了。

我们可以枚举平衡数位的位置，同时在枚举时维护和就行了。

注意最后要减去重复的个数（即多枚举了num-1次0）

 代码实现：

#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#define PI atan(1.0) * 4
#define E 2.718281828
#define rp(i, s, t) for (register int i = (s); i <= (t); i++)
#define RP(i, t, s) for (register int i = (t); i >= (s); i--)
#define ll long long
#define ull unsigned long long
#define mst(a, b) memset(a, b, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define debug printf("acn");
using namespace std;
inline int read()
{
    int a = 0, b = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            b = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        a = (a << 3) + (a << 1) + c - '0';
        c = getchar();
    }
    return a * b;
}
int a[20],num;
ll dp[20][20][10005];
ll dfs(int pos,int k,int sum,int lead,int limit){
    if(pos==0) return sum==0;
    if(sum<0) return 0;
    if(!lead&&!limit&&dp[pos][k][sum]!=-1) return dp[pos][k][sum];
    int up=limit?a[pos]:9;
    ll ans=0;
    rp(i,0,up){
        ans+=dfs(pos-1,k,sum+(pos-k)*i,lead&&i==0,limit&&i==a[pos]);
    }
    if(!limit&&!lead) return dp[pos][k][sum]=ans;
    return ans;
}
ll solve(ll x){
    if(x==-1) return 0;
    num=0;
    while(x) a[++num]=x%10,x/=10;
    ll ret=0;
    RP(i,num,1) ret+=dfs(num,i,0,1,1);
    return ret-num+1;
}
int main(){
    mst(dp,-1);
    int T=read();
    ll l,r;
    while(T--){
        scanf("%I64d%I64d",&l,&r);
        printf("%I64dn",solve(r)-solve(l-1));
    }
    return 0;
}

 

最后

以上就是悦耳大象为你收集整理的hdu3709——数位dp+枚举的全部内容，希望文章能够帮你解决hdu3709——数位dp+枚举所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。