首页 > 代码库 > HDU - 3555 Bomb (数位DP)
HDU - 3555 Bomb (数位DP)
题意:求1-n里有多少人包括”49“的数字
思路:数位DP,分三种情况:到第i位没有49的情况。到第i位没有49且最高位是9的情况。到第i位有49的情况,将三种情况都考虑进去就是了
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; long long dp[30][3], n; int arr[30]; void init() { dp[0][0] = 1; dp[0][1] = dp[0][2] = 0; for (int i = 1; i < 25; i++) { dp[i][0] = dp[i-1][0]*10 - dp[i-1][1]; dp[i][1] = dp[i-1][0]; dp[i][2] = dp[i-1][1] + dp[i-1][2]*10; } } long long cal(long long n) { int len = 0; while (n) { arr[++len] = n%10; n /= 10; } arr[len+1] = 0; int flag = 0; long long ans = 0; for (int i = len; i >= 1; i--) { ans += dp[i-1][2] * arr[i]; if (flag) ans += dp[i-1][0] * arr[i]; else if (arr[i] > 4) ans += dp[i-1][1]; if (arr[i+1] == 4 && arr[i] == 9) flag = 1; } if (flag) ans++; return ans; } int main() { int t; scanf("%d", &t); init(); while (t--) { cin >> n; cout << cal(n) << endl; } return 0; }
HDU - 3555 Bomb (数位DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。