首页 > 代码库 > 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 }
hdu 3709 Balanced Number
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。