首页 > 代码库 > Hdu3079Balanced Number数位dp
Hdu3079Balanced Number数位dp
枚举支点,然后就搞,记录之前的点的力矩和。
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>#include<math.h>using namespace std;typedef long long LL;LL up[100];LL dp[30][30][2000];LL dfs(LL x,LL pos,LL pre,LL flag){ if(x<=0) return pre==0; if(pre<0) return 0; if(!flag&&~dp[x][pos][pre]) return dp[x][pos][pre]; LL limit= flag? up[x]: 9,ret= 0; for(LL i = 0;i<= limit;i++){ ret+=dfs(x-1,pos,pre+(x - pos )* i ,flag&&i==limit) ; } return flag? ret : dp[x][pos][pre]= ret;}LL solve(LL x){ LL len=0; while(x){ up[++len]=x%10; x/=10; } LL ans=0; for(LL i = 1;i<= len;i++) ans+=dfs(len,i,0,1); return ans-len ;}int main(){ LL Icase;LL n,m; scanf("%d",&Icase); memset(dp,-1,sizeof(dp)); while(Icase--){ cin>>n>>m; cout<<solve(m) - solve(n-1) <<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。