【HDU 3555】原题直通车：
代码：
// 31MS 900K 909 B G++ #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[20];
__int64 dp[20][11];
void digit_dp() {
memset(dp, 0LL, sizeof(dp));
dp[0][0]=1;
for(int i=1; i<20; ++i)
for(int j=0; j<10; ++j)
for(int k=0; k<10; ++k) {
if(j==4&&k==9) continue;
dp[i][j]+=dp[i-1][k];
}
}
__int64 Count(__int64 x) {
__int64 u=x, ret=0LL;
int t=0;
memset(a, 0, sizeof(a));
while(u) a[++t]=u%10, u/=10;
for(int i=t; i>=1; --i) {
for(int j=0; j<a[i]; ++j) ret+=dp[i][j];
if(a[i]==9&&a[i+1]==4){
ret--; break;
}
}
return ret;
}
int main() {
int T; scanf("%d",&T);
digit_dp();
while(T--) {
__int64 n;
scanf("%I64d",&n);
__int64 ans=Count(n);
printf("%I64d\n",n-ans);
}
return 0;
}
【HDU 2089】原题直通车：
代码：
// 15MS 844K 921 B C++ #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dp[10][10];
void digit_dp() {
memset(dp, 0, sizeof(dp));
dp[0][0]=1;
for(int i=1; i<8; ++i)
for(int j=0; j<10; ++j)
for(int k=0; k<10; ++k) {
if(j==4||k==4||(j==6&&k==2)) continue;
dp[i][j]+=dp[i-1][k];
}
}
int a[10];
int Count(int x) {
memset(a, 0, sizeof(a));
int u=x, ret=0, t=0;
while(u) a[++t]=u%10, u/=10;
for(int i=t; i>=1; --i) {
for(int j=0; j<a[i]; ++j){
ret+=dp[i][j];
}
if(a[i+1]==6){
if(a[i]==2) break;
if(a[i]>2)ret-=dp[i][2];
}
if(a[i]==4) break;
}
return ret;
}
int main() {
int n, m;
digit_dp();
while(~scanf("%d%d",&n,&m)&&n+m)
printf("%d\n",Count(m+1)-Count(n));
return 0;
}