HDOJ 2089——デジタルDP
いいえ62
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14517 Accepted Submission(s): 4663
Problem Description
杭州人はバカな人を62人と呼んでいる.
杭州交通管理局はよくタクシーのナンバープレートを拡充して、最近良いニュースが出てきて、後でナンバープレートをつけて、もう不吉な数字を含んでいません.そうすれば、個別のタクシーの運転手と乗客の心理的な障害を解消して、もっと安全に大衆にサービスすることができます.
不吉な数字は4または62を含むすべての番号です.例:
62315 73418 88914
いずれも不吉な番号に属している.ただし、61152は6と2を含んでいるが62連番ではないので不吉な数字の列ではない.
あなたの任務は、毎回与えられたナンバープレート区間番号について、交管局が今回また実際に何台の新しいタクシーにナンバープレートを与えたかを推定することです.
Input
入力はすべて整数対n,m(0
Output
各整数ペアについて、1行の位置を占める不吉な数字を含まない統計個数を出力します.
Sample Input
Sample Output
Author
qianneng
Source
新学期を迎えるスーパーEasy版ウォーミングアップ
Recommend
lcy | We have carefully selected several similar problems for you: 2094 2091 2093 2086 2085
考え方はdfsの各ビットの数字で、ビットごとにdfsすればいいです.
状態遷移方程式を直接適用する方法もあります.
状態遷移方程式は,dp[i][0]=8*dp[i−1][0]+dp[i−1][1],dp[i][1]=7*dp[i−1][0]+dp[i−1][1]である.
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 14517 Accepted Submission(s): 4663
Problem Description
杭州人はバカな人を62人と呼んでいる.
杭州交通管理局はよくタクシーのナンバープレートを拡充して、最近良いニュースが出てきて、後でナンバープレートをつけて、もう不吉な数字を含んでいません.そうすれば、個別のタクシーの運転手と乗客の心理的な障害を解消して、もっと安全に大衆にサービスすることができます.
不吉な数字は4または62を含むすべての番号です.例:
62315 73418 88914
いずれも不吉な番号に属している.ただし、61152は6と2を含んでいるが62連番ではないので不吉な数字の列ではない.
あなたの任務は、毎回与えられたナンバープレート区間番号について、交管局が今回また実際に何台の新しいタクシーにナンバープレートを与えたかを推定することです.
Input
入力はすべて整数対n,m(0
Output
各整数ペアについて、1行の位置を占める不吉な数字を含まない統計個数を出力します.
Sample Input
1 100
0 0
Sample Output
80
Author
qianneng
Source
新学期を迎えるスーパーEasy版ウォーミングアップ
Recommend
lcy | We have carefully selected several similar problems for you: 2094 2091 2093 2086 2085
考え方はdfsの各ビットの数字で、ビットごとにdfsすればいいです.
状態遷移方程式を直接適用する方法もあります.
状態遷移方程式は,dp[i][0]=8*dp[i−1][0]+dp[i−1][1],dp[i][1]=7*dp[i−1][0]+dp[i−1][1]である.
/*
ID: xinming2
PROG: stall4
LANG: C++
*/
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <map>
#include <string>
#include <stack>
#include <cctype>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <cassert>
using namespace std;
///#define Online_Judge
#define outstars cout << "***********************" << endl;
#define clr(a,b) memset(a,b,sizeof(a))
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
#define mk make_pair
#define FOR(i , x , n) for(int i = (x) ; i < (n) ; i++)
#define FORR(i , x , n) for(int i = (x) ; i <= (n) ; i++)
#define REP(i , x , n) for(int i = (x) ; i > (n) ; i--)
#define REPP(i ,x , n) for(int i = (x) ; i >= (n) ; i--)
const int MAXN = 100000 + 50;
const int sigma_size = 26;
const long long LLMAX = 0x7fffffffffffffffLL;
const long long LLMIN = 0x8000000000000000LL;
const int INF = 0x7fffffff;
const int IMIN = 0x80000000;
#define eps 1e-8
const int MOD = (int)1e9 + 7;
typedef long long LL;
const double PI = acos(-1.0);
typedef pair<int , int> pi;
#define Bug(s) cout << "s = " << s << endl;
///#pragma comment(linker, "/STACK:102400000,102400000")
int dp[10][2] , digit[10];///dp[i][0] i 4 62 ，dp[i][j] i 4 62 6
int dfs(int len , bool state , bool fp)///state 6，fp
{
if(!len)return 1;
if(!fp && dp[len][state] != -1)return dp[len][state];
int res = 0;
int maxi = fp ? digit[len] : 9;
for(int i = 0 ; i <= maxi ; i++)
{
if(i == 4 || state && i == 2)continue;
res += dfs(len - 1 , i == 6 , fp&&i == maxi);
}
if(!fp)dp[len][state] = res;
return res;
}
int f(int n)
{
int len = 0;
while(n)
{
digit[++len] = n % 10;
n /= 10;
}
return dfs(len , false ,true);
}
int main()
{
int a , b;
clr(dp , -1);
while(~scanf("%d%d" , &a , &b) ,a || b)
{
printf("%d
" , f(b) - f(a - 1));
}
return 0;
}