首页 > 代码库 > hdu 3709 Balanced Number

hdu 3709 Balanced Number

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

题意:在一个区间内有多少个,可以一这个数中的一个数字为支点,两边的数字乘上边距的和相等。

数位dp,枚举支点。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define ll __int64 5 using namespace std; 6  7 ll dp[21][21][2000]; 8 int num[30]; 9 10 ll dfs(int pos,int cen,int sum,bool flag)11 {12     if(pos==-1)13     {14         if(sum==0) return 1;15         else return 0;16     }17     if(sum<0) return 0;18     if(!flag&&dp[pos][cen][sum]!=-1) return dp[pos][cen][sum];19     ll ans=0;20     int xx=flag?num[pos]:9;21     for(int i=0; i<=xx; i++)22     {23         ans+=dfs(pos-1,cen,sum+i*(pos-cen),flag&&(i==xx));24     }25     if(!flag) dp[pos][cen][sum]=ans;26     return ans;27 }28 29 ll get(ll n)30 {31     int cnt=0;32     while(n)33     {34         num[cnt++]=n%10;35         n=n/10;36     }37     ll ans=0;38     for(int i=0; i<cnt; i++)39     {40         ans+=dfs(cnt-1,i,0,true);41     }42     return ans-(cnt-1);43 }44 45 int main()46 {47     int t;48     scanf("%d",&t);49     memset(dp,-1,sizeof(dp));50     while(t--)51     {52         ll n,m;53         scanf("%I64d%I64d",&n,&m);54         printf("%I64d\n",get(m)-get(n-1));55     }56     return 0;57 }
View Code

 

hdu 3709 Balanced Number