Description：
不吉利的数字为所有含有4或62的号码。输出n-m之间的吉利数的个数！
Analyse：
数位dp的原理：如果A<B那么，从高位到低位A一定出现某digit小于B‘s。
对于数位dp板，重点是参数的设置！
CODE：
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<string>#include<queue>#include<deque>#include<stack>#include<map>#include<set>#define INF 0x7fffffff#define SUP 0x80000000#define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long LL;const int N=100007;int dig[2][10];LL dp[10][10][2],id;void mod10(int iid,LL n){int id=1;while(n){dig[iid][id++]=n%10;n/=10;}dig[iid][0]=id-1;}//pos：当前位置//pre：前digit//en：是否出现过含4/62的数，如果含的话返回 1；//limit：看前一位是否限制，如果pre=digit[pos+1],那么当前位只能去digit[pos]，否则可以取到0-9！ 见<span style="color:#FF0000;">***</span>处LL dfs(int pos,int pre,int en,int limit) {if(pos<1) return en;if(!limit&&dp[pos][pre][en]!=-1)return dp[pos][pre][en];int last=limit?dig[id][pos]:9; //<span style="color:#FF0000;">***</span>=_=|LL ret=0;for(int i=0;i<=last;i++)ret+=dfs(pos-1,i,en||(pre==6&&i==2)||i==4,limit&&(i==last));if(!limit)//<span style="color:#FF0000;">为什么</span>，dp要计入没限制的值，，假如有限制，你认为dp[pos][pre][en]还会一样么？，，0-digit[pos],而不是0-9，，而digit[pos]又各异！dp[pos][pre][en]=ret;return ret;}int main(){LL n,m;while(scanf("%I64d%I64d",&n,&m)==2,n+m){LL nn,mm;mem(dp,-1);mod10(0,–n);mod10(1,m);id=0;nn=dfs(dig[id][0],0,0,1);id=1;mm=dfs(dig[id][0],0,0,1);printf("%I64d\n",LL(m-n)-(mm-nn));//s-补集}return 0;}
送给中意的TA，背面写上：某年某月某日，
