第一道數位dp，屬于基礎模板，又自卑小時沒學好數數了，只是不清楚為什么大家的dp定義都是相同的，很顯然么，難道我寫的是怪胎。。。

/* ID:esxgx1 LANG:C++ PROG:hdu3555 */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std;#define LN 21 unsigned 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，開頭無9dp[i][1] = dp[i-1][0] + dp[i-1][1]; // 無49, 開頭是9dp[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_JUDGEfreopen("in.txt", "r", stdin);#endifint 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++

轉載于:https://www.cnblogs.com/e0e1e/p/hdu_3555.html

總結

以上是生活随笔為你收集整理的HDU 3555 - Bomb的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。