hdu2089 不要62

不要62Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14050 Accepted Submission(s): 4509


Problem DescriptionInputOutputSample InputSample OutputAuthor#include <iostream>#include <stdio.h>#include <string.h>using namespace std;int pri[20],dp[10][3];//dp[0]不含４６２的个数dp[1]表示不含462的以２开头的个数，dp[2]不正确的数int init(){ dp[0][0]=1; for(int i=1;i<8;i++){ dp[i][0]=dp[i-1][0]*9-dp[i-1][1];//在不含４６２的数，加上不为４的数９个数，减去以２开头的数加了６ dp[i][1]=dp[i-1][0];//前面加上２ dp[i][2]=dp[i-1][2]*10+dp[i-1][0]+dp[i-1][1];//不正确的数１０个数任意加，正确的数加４，以２开头的加上６ }}int solve(int x){ int cnt=0,ans=0; while(x){ pri[++cnt]=x%10; x/=10; } bool flag=false; pri[cnt+1]=0; for(int i=cnt;i;i--){ ans+=dp[i-1][2]*pri[i]; if(flag)ans+=dp[i-1][0]*pri[i]; else { if(pri[i]>4)ans+=dp[i-1][0]; if(pri[i]>6)ans+=dp[i-1][1]; if(pri[i+1]==6&&pri[i]>2)ans+=dp[i][1]; } if((pri[i+1]==6&&pri[i]==2)||pri[i]==4) flag=true; } return ans;}int main(){ int n,m; init(); while(scanf("%d%d",&n,&m)!=EOF&&n+m){ printf("%d\n",m-n+1-solve(m+1)+solve(n)); } return 0;}