首页 > 代码库 > hdu3709(求区间内平衡数的个数)数位dp
hdu3709(求区间内平衡数的个数)数位dp
题意:题中平衡数的定义: 以一个位置作为平衡轴,然后左右其他数字本身大小作为重量,到平衡轴的距离作为全职,实现左右平衡(即杠杆原理平衡)。然后为区间[x,y]内平衡数的个数。 (0 ≤ x ≤ y ≤ 1018)
解法:数位dp。如果一个数的平衡数,那么它的平衡轴位置是确定的。原来一直尝试数位dp在dfs时候列举平衡轴的位置,后来才意识到可以提前枚举平衡轴位置,然后再dfs,这样比较好写。dp[mid][pre][wei];表示对称轴是mid,计算第pre个位置以后需要力矩大小wei的数的个数。
ps:这个题关键是跟着适牛学了点东西,首先原来自己写了一个now的无用的东西一维记录前一个数字是啥(受前边题目影响,习惯性思维),但是后来发现明显没用。虽然提交A掉了,但是我又尝试去掉那一维试了一下,发现wa了,半天也没发现错哪了,后来适牛提醒说有可能是数组越界了。最后才发现真相:由于原来多了一维,为数组越界提供了可靠的空间,这也是为什去掉之后才会wa的原因。开大了点wei的那一维就又AC了。还从适牛那里学到:由于mid确定后,dp是不变的,所以只需要memset一次就够了,加上wei>=(len*(len+1)/2*9)+2的剪枝后,做到了0ms。
代码:
/****************************************************** * author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=10100; const int INF=1000000007; LL dp[20][20][410]; int num[20]; LL l,r; int len=0; LL dfs(int mid,int pre,int wei,bool limit) { if(wei<0||wei>=(len*(len+1)/2*9)+2) return 0; if(pre==0) return wei==0; if(!limit&&dp[mid][pre][wei]!=-1) return dp[mid][pre][wei]; int en=limit ? num[pre-1]:9; LL ans=0; for(int i=0; i<=en; i++) { if(pre-1==mid&&i==0&&wei==0) continue; ans+=dfs(mid,pre-1,wei+(pre-1-mid)*i,limit&&(i==en)); } return (!limit) ? dp[mid][pre][wei]=ans : ans; } LL solve(LL n) { if(n<0) return 0; int p=0; while(n) { num[p++]=n%10; n/=10; } len=p/2; LL ans=0; for(int mid=p-1; mid>=0; mid--) { for(int i=0; i<=num[p-1]; i++) { if(i==0&&mid==p-1) continue; ans+=dfs(mid,p-1,(p-1-mid)*i,i==num[p-1]); } } return ans+1; } int main() { int t; cin>>t; memset(dp,-1,sizeof dp); while(t--) { scanf("%I64d%I64d",&l,&r); cout<<solve(r)-solve(l-1)<<‘\n‘; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。