1024问

hdu4734——数位dp（减去的艺术）

Eva ·
更新时间:2024-09-21
· 688 次阅读

题目链接：https://vjudge.net/problem/HDU-4734

题目大意：求区间[l,r]内满足数x的F(x)<=F(a)的数的个数。

对于一个n位的数(AnAn-1An-2....A1)，F(x)=An*2^(n-1)+An-1*2^(n-2)+...+A1*1.

题解：

首先我们肯定要维护一个状态sum表示枚举到pos位数的前面的数位的F(x)值，最后判断一下是否大于F(a)就行了。

因为F(x)最大为4599.所以这样是存的下的。

但是我们还需要再开一维存预先求出来的F(a)，用来记录每一操作时对应的F(a)。

如果不用的话直接每次操作时都memset会超时。

但是这样一来空间又不够了，因此我们需要考虑一种状态既不需要存F(a)，memset又可以在外面执行。

这里就体现了减去的艺术了。

定义新的状态为dp[pos][sum]表示枚举到当前pos位，后面还需要凑sum的权值和的个数。

至于为什么这样是可行的呢。

我们可以这样考虑，虽然F(a)是变的，但是每次大的F(a)总会用到小的F(a)。

而小的F(a)不会因为大的F(a)的改变而改变，因此大的sum会用到小的sum，但是小的sum不会因为F(a)的改变而改变。

代码实现：

#pragma GCC optimize(2) #include #include #include #include #include #include #include #include #include #include #include #define PI atan(1.0) * 4 #define E 2.718281828 #define rp(i, s, t) for (register int i = (s); i = (s); i--) #define ll __int64 #define ull unsigned long long #define mst(a, b) memset(a, b, sizeof(a)) #define lson l, m, rt << 1 #define rson m + 1, r, rt << 1 | 1 #define pii pair #define mp make_pair #define pb push_back #define debug printf("ac\n"); using namespace std; inline int read() { int a = 0, b = 1; char c = getchar(); while (c '9') { if (c == '-') b = -1; c = getchar(); } while (c >= '0' && c <= '9') { a = (a << 3) + (a << 1) + c - '0'; c = getchar(); } return a * b; } int a[20]; ll dp[20][5005]; ll MAX; int num; ll dfs(int pos,int sum,int lead,int limit){ if(pos==-1) return sumMAX) return 0; if(!lead&&!limit&&dp[pos][MAX-sum]!=-1) return dp[pos][MAX-sum]; int up=limit?a[pos]:9; ll ans=0; rp(i,0,up){ ans+=dfs(pos-1,sum+i*(1<<pos),lead&&i==0,limit&&i==a[pos]); } if(!limit&&!lead) return dp[pos][MAX-sum]=ans; return ans; } ll solve(ll x){ num=0; while(x) a[num++]=x%10,x/=10; return dfs(num-1,0,1,1); } int main(){ int T=read(); mst(dp,-1); int kcase=0; while(T--){ ll a,b; scanf("%lld%lld",&a,&b); MAX=0; ll temp=1; while(a){ MAX+=a%10*temp; temp*=2; a/=10; } // printf("%lld\n",MAX); printf("Case #%d: %lld\n",++kcase,solve(b)-solve(0)+1); } return 0; }
作者：木每立兄豪



数位dp dp hdu 艺术

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
PHP生成随机字符串实例代码（字母+数字）
Janna 2020-05-26
611
详解Linux下出现permission denied的解决办法
Delfina 2020-05-06
962
asp 使用正则表达式替换word中的标签，转为纯文本
Iona 2021-07-23
518
highcharts.js数据绑定方式代码实例
Delfina 2020-02-12
571
艺咚咚 — 打开艺术品全新时代
Kande 2020-06-16
931
CSS 还能这样玩？奇思妙想渐变的艺术
Cybill 2021-12-13
709
C++数位DP复杂度统计数字问题示例详解
Zada 2021-12-16
1498
c++基础算法动态DP解决CoinChange问题
Beth 2021-12-16
119
详解树形DP
Bliss 2021-12-16
310
详解DAG上的DP
Viridis 2021-12-16
355
os x yosemite dp6下载 os x 10.10 dp6官方下载地址
Brigitte 2022-02-21
574
os x yosemite dp5下载地址 os x 10.10 dp5更新内容
Vanna 2022-02-21
1092
Python面向对象编程之封装的艺术你了解吗
Bonnie 2022-07-15
1658
android中px、sp与dp之间进行转换详解
Miette 2022-08-21
1484
C语言文字艺术之数据输入输出
Elita 2022-10-15
1422
C语言 深入理解动态规划之计数类DP
Fern 2022-10-24
1277
C语言深入探究动态规划之区间DP
Dabria 2022-10-24
944
C语言深入探究动态规划之线性DP
Tricia 2022-10-24
913
C语言数学问题与简单DP01背包问题详解
Elsa 2022-10-24
1578
C语言动态规划点杀dp算法LeetCode炒股习题案例解析
Serafina 2022-10-24
761