首页 > 代码库 > hdu 3709 Balanced Number(数位dp)
hdu 3709 Balanced Number(数位dp)
http://acm.hdu.edu.cn/showproblem.php?pid=3709
平衡数。枚举支点的位置,同时记录力臂。
dp[i][j][k]表示当前处理到第i个数,支点的位置是j,当前的力臂是k。因此判断某个数是否是平衡数,只需判断递归终点时力臂是否为0。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <list> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL __int64 #define eps 1e-12 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 4010; int dig[20]; LL dp[20][20][10010]; LL dfs(int len, int mid, int k, int up) //len表示当前第len位,mid表示支点位置,k表示当前力臂,up是否与到达上界。 { if(len == 0) return k == 0; if(k < 0) //到达某一位时力臂小于0,那么以后也不会有等于0的情况了,直接退出 return 0; if(!up && dp[len][mid][k] != -1) return dp[len][mid][k]; int n = up ? dig[len] : 9; LL res = 0; for(int i = 0; i <= n; i++) { res += dfs(len-1,mid,k+(len-mid)*i,up&&i==n); } if(!up) dp[len][mid][k] = res; return res; } LL cal(LL num) { int len = 0; while(num) { dig[++len] = num % 10; num /= 10; } LL ans = 0; for(int i = 1; i <= len; i++) //枚举支点。对于dp数组的初始化要放在外面,要不怎么记忆化 { ans += dfs(len,i,0,1); } return ans - len +1; } int main() { int test; LL x,y; scanf("%d",&test); memset(dp,-1,sizeof(dp)); while(test--) { scanf("%I64d %I64d",&x,&y); printf("%I64d\n",cal(y) - cal(x-1)); } return 0; }
hdu 3709 Balanced Number(数位dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。