HDU 2089 数位DP 入门题

本文主要是介绍HDU 2089 数位DP 入门题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目
提意:在n - m中有多少个数不含【4】 和 【62】

dp[i][j] 表示第i位为j的答案数

这样
1. j = 6 dp[i][j] += dp[i - 1][k] (k = 0 ~ 9 ^ k != 4 | 2)
2. j = 4 dp[i][j] = 0

对于数字N 在计算0 - N 的区间答案时 从高位枚举i（自右向左的位数） 表示某个数从最高位开始 第 i 位小于N的第i位 比如 对于数 56800 在i为4时 指代的数为50000 ～ 55999 答案 ans += dp[4][k] k = 0 ~ 5

为什么 ans += dp[4][k] k = 0 ~ 5

由迭代dp的过程可以看出 dp[i][k] 实际上 算得只是满足i位的答案数 大于k位的并没有包含在dp[i][k]中 在上面的例子中 dp[4][k] (k = 0 ~ 5) 的实际指代的区间为 0000 ~ 5999 并不是50000 ～ 55999的答案 但是 我们可以在0000 ~ 5999中每个数加上50000 得到0000 ~ 5999 并且又题意易知 这样不会改变任何一个数的正确性

综上 50000 ～ 55999 的正确个数 等于 0000 ~ 5999 的正确个数

正是这个原因 要在计算答案时 及时排去 形如 ###4*** 和 ###62***的答案

代码如下:

#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 10;
int dp[maxn][10];int f(char* num){int ans = 0 , len = strlen(num);
//    puts(num);for(int i = len - 1;i > 0;--i){for(int j = 0;j < num[i] - '0';++j){if(j == 4 || (num[i + 1] - '0' == 6 && j == 2)){continue;}else ans += dp[i][j];
//            pf("%d %d\n",i,j);}if(num[i] - '0' == 4 || (num[i + 1] - '0' == 6 && num[i] - '0' == 2 ) ) {
//            pf("break  %d",i);break;}}return ans;
}int main(){for(int i = 0;i < 10;++i){dp[1][i] = 1;}dp[1][4] = 0;for(int i = 2;i <= 7;++i){for(int j = 0;j < 10;++j){if(j == 4){dp[i][j] = 0;continue;}for(int k = 0;k < 10;++k){if(j == 6 && k == 2){continue;}else dp[i][j] += dp[i - 1][k];}}}int a,b;char num1[maxn],num2[maxn];while( sf("%d%d",&a,&b) ){if(!a && !b) break;b++;sprintf(num1,"%d",a);sprintf(num2,"%d",b);int len1 = strlen(num1),len2 = strlen(num2);num1[len1] = '#' ,num1[len1 + 1] = '\0';num2[len2] = '#' ,num2[len2 + 1] = '\0';strrev(num1);strrev(num2);pf("%d\n",f(num2) - f(num1));}return 0;
}

DFS版本：真的简单明了

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define sf scanf
#define pf printf
#define N 20
using namespace std;int dp[15][2];//dp[i][st]保存在填写第i位时 之前的状态为st时的满解 如i = 3时 表示 000 ～ 999内不含4 和 62 的数的个数int digit[15];
int dfs(int i,bool st,bool flag){   //第i位数 st之前一位是或者不是6  flag前缀是否已为上界if(i == 0) return !flag; //递归到0位 前面的len位全部是按题意填写的数字 flag为1时 这个数字是上界 flag为0时 这个数字是在范围内的一个正确解if(!flag && dp[i][st] != -1) return dp[i][st];//flag为0时 可以取满解 且在dp[i][st]已经计算过时 可以直接返回dp值int limit = !flag ? 9 : digit[i];int ans = 0;for(int j = 0;j <= limit;++j){if(!( st && j == 2 || j == 4 ) )ans += dfs(i - 1,j == 6,flag && j == limit);}if(!flag) dp[i][st] = ans;//如果这一次计算的是满解 则赋值给dp[i][st]return ans;
}int solve(int n){int len = 0;while(n){digit[++len] = n % 10;n = n /10;}return dfs(len,0,1); //前缀已为上界
}int main(){int l,r;memset(dp,-1,sizeof(dp));while( sf("%d%d",&l,&r) != EOF && l && r){pf("%d\n",solve(r + 1) - solve(l));}return 0;
}

这篇关于HDU 2089 数位DP 入门题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---