首页 > 代码库 > HDU 3555 - Bomb
HDU 3555 - Bomb
第一道数位dp,属于基础模板,又自卑小时没学好数数了,只是不清楚为什么大家的dp定义都是相同的,很显然么,难道我写的是怪胎。。。
/*ID:esxgx1LANG:C++PROG:hdu3555*/#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;#define LN 21unsigned long long dp[LN + 1][3];void work(int ln){ dp[0][0] = 1; for(int i=1; i<=ln; ++i) { dp[i][0] = dp[i-1][0] * 9 + dp[i-1][1] * 8; // 无49,开头无9 dp[i][1] = dp[i-1][0] + dp[i-1][1]; // 无49, 开头是9 dp[i][2] = dp[i-1][2] * 10 + dp[i-1][1]; // 有49// printf("i=%d, %I64u %I64u %I64u\n", i, dp[i][0], dp[i][1], dp[i][2]); }}unsigned long long solve(int i, unsigned long long N, int &extra){ unsigned long long prefix = N/10; int curr = N % 10; int extra0 = extra; unsigned long long rslt = N % 10 * dp[i-1][2]; if (curr >= 9 && prefix % 10 == 4) extra = 1; if (prefix) rslt += solve(i+1, prefix, extra0); if (extra0) { rslt += curr * (dp[i-1][0] + dp[i-1][1]); extra = 1; } else if (curr > 4) rslt += dp[i-1][1]; return rslt;}int main(void){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif int T; cin >> T; if (T) { work(LN); do { unsigned long long N; cin >> N; int extra = 0; cout << solve(1, N, extra) + (extra ? 1 : 0)<< endl; --T; }while(T); } return 0;}
2014-07-31 20:55:00 | Accepted | 3555 | 156MS | 348K | 1257 B | G++ |
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。