首页 > 代码库 > HDU 2089 不要62(数位DP,三种姿势)
HDU 2089 不要62(数位DP,三种姿势)
HDU 2089 不要62(数位DP,三种姿势)
ACM
题目地址:HDU 2089
题意:
中文题意,不解释。
分析:
- 100w的数据,暴力打表能过
- 先初始化dp数组,表示前i位的三种情况,再进行推算
- 直接dfs,一遍搜一变记录,可能有不饥渴的全部算和饥渴的部分算情况,记录只能记录全部算(推荐看∑大的详细题解Orz)
代码:
1. 暴力 (以前写的)
/* * Author: illuz <iilluzen[at]gmail.com> * File: 2089_bf.cpp * Create Date: 2014-03-31 20:28:46 * Descripton: brute force way */ #include <cstdio> #define RII(x,y) scanf("%d%d",&x,&y) #define PIN(x) printf("%d\n",x) #define repf(i,a,b) for(int i=(a);i<=(b);i++) const int N = 1000010; int f[N], n, m; bool check(int r) { while (r) { if (r % 10 == 4) return false; if (r % 100 == 62) return false; r /= 10; } return true; } void init() { repf (i, 1, 1000000) if (check(i)) f[i] = f[i - 1] + 1; else f[i] = f[i - 1]; } int main() { init(); while (RII(n, m) && (n || m)) { PIN(f[m] - f[n - 1]); } return 0; }
2. DP_1
/* * Author: illuz <iilluzen[at]gmail.com> * File: 2089.cpp * Create Date: 2014-07-26 09:55:48 * Descripton: */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define RII(x,y) scanf("%d%d",&x,&y) #define PIN(x) printf("%d\n",x) #define repf(i,a,b) for(int i=(a);i<=(b);i++) #define repd(i,a,b) for(int i=(a);i>=(b);i--) const int N = 10; int n, m; int bits[N]; int dp[N][3]; // [len][x] // 0->luck // 1->luck and highest is 2 // 2->unluck void init() { dp[0][0] = 1; // len is 0 and luck is 1, becauses the dp[1][1] will equal it. dp[0][1] = dp[0][1] = 0; repf(i, 1, N - 1) { dp[i][0] = dp[i - 1][0] * 9 // i-1_luck without 4 - dp[i - 1][1]; // and without 62 dp[i][1] = dp[i - 1][0]; // equal to i-1_luck_2 + '6' dp[i][2] = dp[i - 1][2] * 10 // unluck is always unluck + dp[i - 1][0] // i-1_luck + '4' + dp[i - 1][1]; // i-1_luck_2 + '6' } } int solve(int num) { int len = 0, rec = num, ans, flag; // get bits array while (num) { bits[++len] = num % 10; num /= 10; } bits[len + 1] = 0; ans = 0; // the unluck num flag = 0; // if appear unluck repd (i, len, 1) { ans += dp[i - 1][2] * bits[i]; // unluck is always unluck if (flag) { // if unluck appeared ans += dp[i - 1][0] * bits[i]; // all luck become unluck } else { if (bits[i] > 4) { ans += dp[i - 1][0]; // i-1_luck + '4' } if (bits[i] > 6) { ans += dp[i - 1][1]; // i-1_luck_2 + '6' } if (bits[i + 1] == 6 && bits[i] > 2) { ans += dp[i][1]; } } if (bits[i] == 4 || (bits[i + 1] == 6 && bits[i] == 2)) { flag = 1; } } return rec - ans; } int main() { init(); while (~RII(n, m) && (n || m)) { PIN(solve(m + 1) - solve(n)); } return 0; }
3. DP_2(DFS)
/* * Author: illuz <iilluzen[at]gmail.com> * File: 2089_dfs.cpp * Create Date: 2014-07-26 15:21:12 * Descripton: dfs version */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define RII(x,y) scanf("%d%d",&x,&y) #define PIN(x) printf("%d\n",x) const int N = 10; int bits[N], dp[N][2]; // dp[i][is6] is the number of i-len digits with (if prevent number is 6), its digits are from 0-9 // the rest length, Is the prevent digit 6, Is the digit max int dfs(int len, bool is6, bool ismax) { if (len == 0) return 1; if (!ismax && dp[len][is6] >= 0) // dp return dp[len][is6]; int cnt = 0, mmax = (ismax? bits[len] : 9); for (int i = 0; i <= mmax; i++) { if (i == 4 || is6 && i == 2) // unluck digit continue; cnt += dfs(len - 1, i == 6, ismax && i == mmax); } return ismax ? cnt : dp[len][is6] = cnt; // remember the result } int solve(int num) { int len = 0; while (num) { bits[++len] = num % 10; num /= 10; } return dfs(len, false, true); } int main() { int n, m; memset(dp, -1, sizeof(dp)); while (~scanf("%d%d", &n, &m) && (n || m)) { PIN(solve(m) - solve(n - 1)); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。