﻿HDU 2089 不要62-Ocrosoft

# 不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 34822    Accepted Submission(s): 12629

Problem Description

62315 73418 88914

Input

Output

Sample Input
```1 100
0 0
```

Sample Output
```80
```

Author
qianneng

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 7 + 10;
using namespace std;
int dp[10][10];//数字7位
void ini()
{
ms(dp);
dp[0][0] = 1;
for (int i = 1; i <= 7; i++)
{
for (int j = 0; j < 10; j++)//枚举第i位
{
for (int k = 0; k < 10; k++)//枚举下一位
{
if (j != 4 && !(j == 6 && k == 2))//第i位不是4，并且是6的时候下一位不能是2
{
dp[i][j] += dp[i - 1][k];
}
}
}
}
}
int solve(int n)//传入是n，返回时1到n的满足条件的个数
{
int ret = 0;
ini();
int dig[10] = { 0 }, len = 0;
while (n / 10 != 0 || n % 10 != 0)
{
dig[++len] = n % 10;
n /= 10;
}
for (int i = len; i; i--)
{
for (int j = 0; j < dig[i]; j++)
{
if (j != 4 && !(dig[i + 1] == 6 && j == 2))//这里数字是倒着存的
ret += dp[i][j];
}
if (dig[i] == 4 || (dig[i] == 2 && dig[i + 1] == 6))break;//遇到不满足的就结束
}
return ret;
}
int main()
{
int n, m;
while (cin >> n >> m&&n + m)//n,m>0
{
cout << solve(m + 1) - solve(n) << endl;//不加一当n，m相同的时候就会是0。
}
return 0;
}
```