文章目录
- 数位DP
- 例题
- HDU-2089
- 法一、递推公式
- 法二、记忆化搜索
- HDU-3555
- 法一
- 法二
数位DP
例题
HDU-2089
HDU-2089 不要62
Problem Description 杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。 杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。 不吉利的数字为所有含有4或62的号码。例如： 62315 73418 88914 都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。 你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。 Input 输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。 Output 对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。 Sample Input 1 100 0 0 Sample Output 80
法一、递推公式
#include<bits/stdc .h>
using namespace std;
int a[20];
int dp[20][10];
void init(){
dp[0][0] = 1;
for (int i = 1; i <= 7; i )//题目交代7位数
for (int j = 0; j <= 9; j )
for (int k = 0; k <= 9; k)
if (j != 4 && !(j == 6 && k == 2))
dp[i][j] = dp[i - 1][k];
}
int solve(int x){
int pos = 0;
int ans = 0;
while (x) {
a[ pos] = x % 10;
x /= 10;
}
a[pos 1] = 0;
for (int i = pos; i >= 1; i--){//枚举位数
for (int j = 0; j < a[i]; j ) {//枚举首位
if (a[i 1] != 6 || j != 2)
ans = dp[i][j];
}
if (a[i] == 4 || (a[i 1] == 6 && a[i] == 2))
break; //只要含4或62后面的都不统计了
}
return ans;
}
int main() {
init();
int n, m;
while (~scanf("%d%d", &n, &m) && (n m)) {
printf("%dn", solve(m 1) - solve(n));
}
return 0;
}法二、记忆化搜索
代码语言：javascript复制
#include<bits/stdc .h>
using namespace std;
int a[20];
int dp[20][2];
int dfs(int pos, int pre, int sta, bool limit){
if (pos == -1)
return 1;
if (!limit && dp[pos][sta] != -1) //记忆
return dp[pos][sta];
int up = limit ? a[pos] : 9;
int temp = 0;
for (int i = 0; i <= up; i ){
if (i == 4)
continue;
if (pre == 6 && i == 2)
continue;
temp = dfs(pos - 1, i, i == 6, limit && i == a[pos]);
}
if (!limit)
dp[pos][sta] = temp;
return temp;
}
int solve(int x){
int pos = 0;
while (x){
a[pos ] = x % 10;
x /= 10;
}
return dfs(pos - 1, -1, 0, true);
}
int main(){
int n, m;
while (~scanf("%d%d", &n, &m) && (n m)){
memset(dp, -1, sizeof(dp));
printf("%dn", solve(m) - solve(n - 1));
}
return 0;
}HDU-3555
HDU-3555 Bomb
Problem Description The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point. Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them? Input The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description. The input terminates by end of file marker. Output For each test case, output an integer indicating the final points of the power. Sample Input 3 1 50 500 Sample Output 0 1 15 Hint From 1 to 500, the numbers that include the sub-sequence “49” are “49”,“149”,“249”,“349”,“449”,“490”,“491”,“492”,“493”,“494”,“495”,“496”,“497”,“498”,“499”, so the answer is 15.
求1-n有多少个含49的数，是上一题的反面，去不含49即可。
法一
代码语言：javascript复制#include<bits/stdc .h>
typedef long long ll;
using namespace std;
ll a[100];
ll dp[100][10];
void init() {
dp[0][0] = 1;
for (int i = 1; i <= 63; i )
for (int j = 0; j <= 9; j )
for (int k = 0; k <= 9; k)
if (!(j == 4 && k == 9))
dp[i][j] = dp[i - 1][k];
}
ll solve(ll x) {
int pos = 0;
ll ans = 0;
while (x) {
a[ pos] = x % 10;
x /= 10;
}
a[pos 1] = 0;
for (int i = pos; i >= 1; i--) {
for (int j = 0; j < a[i]; j ) {
if (a[i 1] != 4 || j != 9)
ans = dp[i][j];
}
if (a[i 1] == 4 && a[i] == 9)
break;
}
return ans;
}
int main() {
init();
ll t, n;
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
printf("%lldn", n 1-solve(n 1));
}
return 0;
}法二
代码语言：javascript复制#include<bits/stdc .h>
typedef long long ll;
using namespace std;
ll a[100];
ll dp[100][2];
ll dfs(int pos, int pre, int sta, bool limit) {
if (pos == -1)
return 1;
if (!limit && dp[pos][sta])
return dp[pos][sta];
int up = limit ? a[pos] : 9;
ll temp = 0;
for (int i = 0; i <= up; i ) {
if (pre == 4 && i == 9)
continue;
temp = dfs(pos - 1, i, i == 4, limit && i == a[pos]);
}
if (!limit)
dp[pos][sta] = temp;
return temp;
}
ll solve(ll x) {
int pos = 0;
while (x) {
a[pos ] = x % 10;
x /= 10;
}
return dfs(pos - 1, -1, 0, true);
}
int main() {
ll t, n;
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
memset(dp, 0, sizeof(dp));
printf("%lldn", n 1 - solve(n));
}
return 0;
}原创不易，请勿转载（
本不富裕的访问量雪上加霜） 博主首页：https://blog.csdn.net/qq_45034708
