不要62
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 27292 Accepted Submission(s): 9573
Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如：
62315 73418 88914
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。
Input
输入的都是整数对n、m（0 < n ≤ m < 1000000），如果遇到都是0的整数对，则输入结束。
Output
对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。
Sample Input
1 100
0 0
Sample Output
80
人生中第二道数位DP。
这一题我的做法和上一题那个49数位DP不一样。
我用dp[i][num]来存长度为i的以num为开头的满足题意的数的个数。
说起来有点绕，实际就是以num(0~9)作为开头并且数位长度为i的数中，满足题意的数的个数。
那么dp[i][num]在num等于4时，直接等于0；
在num等于6时，dp[i][num]=sum(dp[i-1][0~1,3~9]);
其他情况，dp[i][num]=sum(dp[i-1][0~9])。
那么对于一个区间(n,m)，我们分别求出0~n-1对应的满足个数和0~m对应的满足个数，进行相减后输出。
那么对于一个数N，先将按数码其存入数组num[]，长度为size，记其满足题意的数的个数为sum，初始值为0，然后从高位开始处理。
对于处理第i位数，先看看之前是否出现过62或者是4，如果有的话就不用继续了；如果没有，那应该首先加上小于num[i]x10^i中满足题意的数，即先加sum(dp[i][0~num[i]-1)；然后看看该位是否为4或者说能否与上一位构成62，如果能的话，立flag。
处理到第1位就OK了，不过由于处理方式，所以在代入值时，要代N+1而不是N。
最后right-left，输出。
//
// main.cpp
// 数位DP-C-不要62
//
// Created by 袁子涵 on 15/10/29.
// Copyright ? 2015年 袁子涵. All rights reserved.
//
// 0ms 1564KB#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>using namespace std;long long int n,m;
long long int dp[10][10];void handle()
{for (int i=0; i<10; i++)if (i!=4)dp[1][i]=1;for (int i=2; i<=9; i++) {for (int j=0; j<=9; j++) {dp[i][j]=0;if (j==4) {dp[i][j]=0;continue;}else{if (j==6) {for (int k=0; k<=9; k++) {if (k==2)continue;dp[i][j]+=dp[i-1][k];}}elsefor (int k=0; k<=9; k++)dp[i][j]+=dp[i-1][k];}}}
}long long int DP(long long int N)
{char num[10];memset(num, 0, sizeof(num));int size=0;long long int sum=0;while (N) {num[++size]=N%10;N/=10;}bool flag=0;for (int i=size; i>=1; i--) {if (flag)break;for (int j=num[i]-1; j>=0; j--){if (num[i+1]==6 && j==2) {continue;}sum+=dp[i][j];}if (num[i]==4 || (num[i]==2 && num[i+1]==6))flag=1;}return sum;
}int main(int argc, const char * argv[]) {memset(dp, 0, sizeof(dp));handle();while (scanf("%lld%lld",&n,&m)!=EOF && (m!=0 || n!=0)) {long long int right,left;right=DP(m+1);left=DP(n);printf("%lld\n",right-left);}return 0;
}