首页 > 代码库 > 【hdu3709】 Balanced Number
【hdu3709】 Balanced Number
http://acm.hdu.edu.cn/showproblem.php?pid=3709 (题目链接)
题意
求范围${[a,b]}$之间的平衡数的个数，所谓平衡数就是以某一位为支点，两侧的力矩相等。
Solution
数位dp记忆化搜索。
一般的数位dp记忆化搜索一定是从高位往低位搜索，传递2个参数：pos，当前dp的位置；lim是否有上限。如果没有上限就可以利用记忆化的${f}$来返回值了。
这道题的话就是枚举支点，然后从高位往低位搜索过去，复杂度大概是${O(20*10*2000)}$，还有多组数据，记忆化了不虚。
细节
LL
代码
// hdu3709#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<ctime>#define LL long long#define inf (1ll<<30)#define MOD 1004535809#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;LL f[20][20][2000],l,r;int t[20],n;LL dfs(int pos,int o,int val,int lim) { //pos当前位置,o支点,val力矩,lim是否有上限 if (pos==0) return val==0; //已经dp完成 if (val<0) return 0; //力矩已经<0 if (!lim && f[pos][o][val]!=-1) return f[pos][o][val]; //已经搜索过了 LL ans=0; int end=lim ? t[pos] : 9; //设置枚举上界 for (int i=0;i<=end;i++) ans+=dfs(pos-1,o,val+(pos-o)*i,lim && i==end); if (!lim) f[pos][o][val]=ans; return ans;}LL solve(LL p) { for (n=0;p;p/=10) t[++n]=p%10; LL ans=0; for (int i=1;i<=n;i++) ans+=dfs(n,i,0,1); return ans-(n-1);}int main() { int T;scanf("%d",&T); memset(f,-1,sizeof(f)); while (T--) { scanf("%lld%lld",&l,&r); printf("%lld\n",solve(r)-solve(l-1)); } return 0;}
【hdu3709】 Balanced Number
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。