Bomb
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
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.
数位统计DP的例题，题目就是让你统计0~n里带49的数有多少个
我是看着书学的(算法竞赛进阶指南p342)，主要的思路也是根据书上来的，所以我的代码还可以帮助同学们理解书上的内容
这道题也是先用动态规划进行预处理，再调用dp数组判断个数，dp[i][j]的意思是位数为i的数中离满足条件还剩几步，比如dp[i][0]就是首位不是4也不是9的（当然后面也没有），dp[i][1]就是首位是9的，dp[i][2]表示已经有49的（也就是满足条件了的）（可以不在首位），那么可以得到状态转移方程
dp[i][0] = 9 * dp[i - 1][0] + 8 * dp[i - 1][1];
dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
dp[i][2] = 10 * dp[i - 1][2] + dp[i - 1][1]; （难点之一）
调用的时候就按照位数判断，每一位的数量就是这一位可能的值乘以下一位的dp[i-1]2，注意当j=4时也要加上下一位的dp[i-1][1]、当j=9时要特判上一位。
还有值得注意的是，比如当n=2349时，若i=4时首位是2的话，那么下一位只能是0~3，而当首位是0 ~1的时候，下一位可以取任意的值，所以我们将限制部分交由下位数判断，比如i=4时，j只判断0 ~1，当i=3时我们默认最高位为2（这样的话i=3判完之后就能筛选出0 ~2200里面的符合条件的数）
但是这样也会带来一些问题，不难想到，当i不是最高位时高位的数会对后来的判断有一定的影响(其中包括这位是9判断上一位是不是4 和判断上几位有没有出现49等)，所以要特判，这也是这种想法的难点所在
代码如下
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[65];
ll dp[65][3];//最高位为i 还有几步就满足(0代表没4也没9 1代表最高位为9 2代表已满足)
ll n;//dp[i][2]是i位数字中满足题意的(允许前导零)如是就是从0000到9999有几个满足的
void prework() {//dp[0][0] = 1;dp[1][0] = 9;dp[1][1] = 1;dp[1][2] = 0;for (int i = 2; i < 21; i++) {dp[i][0] = 9 * dp[i - 1][0] + 8 * dp[i - 1][1];dp[i][1] = dp[i - 1][0] + dp[i - 1][1];dp[i][2] = 10 * dp[i - 1][2] + dp[i - 1][1];//加起来应该是十倍的dp[i-1][0~2]}
}void solve(ll x)
{ll number = x;ll f = 1;ll ans = 0;while (x){a[f++] = x % 10;x /= 10;}a[f--] = 0;//？？for (ll i = f; i >= 0; i--){if (f - i >= 2||i == 0)//两个循环之后才能判断{if (a[i + 1] == 9 && a[i + 2] == 4){ll v, w = 1;for (v = 0; v < i; v++) w *= 10;ans += number % w + 1;//+1吗break;}}for (ll j = 0; j < a[i]; j++)//if (j != 4 && j != 9)ans += dp[i - 1][2];else if (j == 4)//看下一位ans += dp[i - 1][2] + dp[i - 1][1];else if (j == 9)//看上一位{ans += dp[i - 1][2];if (a[i + 1] == 4)ans += (dp[i - 1][0] + dp[i - 1][1]);//如果有四有九那么把下一位的全加上}}printf("%lld\n", ans);
}int main()
{int t;cin >> t;memset(dp, 0, sizeof(dp));prework();while (t--) {scanf("%lld", &n);memset(a, 0, sizeof(a));//printf("%lld\n", solve());solve(n);}return 0;
}
这种关于 long long的题我建议是个变量就要用long long 否则自己都不知道是哪个变量出现了问题