首页 > 代码库 > 几道数位dp

几道数位dp

hdu2089 不要62

/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int> vi;int n,m;int dp[10][3];int bit[10];void ini(){    mset(dp);    dp[0][1]=1;    for(int i=1; i<=6; i++){        dp[i][0] = dp[i-1][1];        dp[i][1] = dp[i-1][1]*9 - dp[i-1][0];        dp[i][2] = dp[i-1][2]*10 + dp[i-1][1] + dp[i-1][0];    }}int solve(int x){    int ans=0,len=0,tmp=x;    bool flag=0;    mset(bit);    while(x){        bit[++len] = x%10;        x/=10;    }    bit[len+1]=0; //为了bit[i+1]=6 && bit[i]>2这一步    for(int i=len;i;i--){//前i位数,第i位不为0,不吉利数为ans        ans += dp[i-1][2]*bit[i];        if(flag){            ans+=dp[i-1][1]*bit[i];            continue;        }        if(bit[i]>4)            ans+=dp[i-1][1];        if(bit[i+1]==6 && bit[i]>2)            ans+=dp[i][0];        if(bit[i]>6)            ans+=dp[i-1][0];        if((bit[i+1]==6 && bit[i]==2) || bit[i]==4)            flag=1;    }    return tmp-ans;}int main(){//    freopen("a.txt","r",stdin);//    freopen(".out","w",stdout);    ini();    while(cin>>n>>m,n|m){        cout<<solve(m+1)-solve(n)<<endl;    }    return 0;}/*DESCRIPTION:先做预处理前i位数,不存在不吉利号码,最高位是2    dp[i][0].......,不存在不吉利号码,最高位包括2    dp[i][1].......,存在不吉利号码                  dp[i][2]dp[i][0] = dp[i-1][1];dp[i][1] = (dp[i-1][1]-dp[i-1][0])*9 + dp[i-1][0]*8 = dp[i-1][1]*9 - dp[i-1][0]           //最高位可以是0dp[i][2] = dp[i-1][2]*10 + dp[i-1][0]*2 + (dp[i-1][1]-dp[i-1][0]) = dp[i-1][2]*10 + dp[i-1][0] + dp[i-1][1] dp[1][0] = 1;dp[1][1] = 9;dp[1][2] = 1;利用solve(n)计算小于n的吉利号码的个数ans = solve(m+1) - solve(n);*/
View Code

hdu3555 bomb 

/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int> vi;int t;ll n;ll dp[20][3];int bit[20];void ini(){    mset(dp);    dp[0][1]=1;    rep(i,1,16){        dp[i][0]=dp[i-1][1];        dp[i][1]=10*dp[i-1][1] - dp[i-1][0];        dp[i][2]=dp[i-1][0] + dp[i-1][2]*10;    }}ll solve(ll x){    int len=0;    while(x){        bit[++len] = x%10;        x/=10;    }    ll ans=0;    bool flag=0;    bit[len+1]=0;    for(int i=len;i;i--){        ans+=dp[i-1][2]*bit[i];        if(flag){            ans+=dp[i-1][1]*bit[i];            continue;        }        if(bit[i]>4)            ans+=dp[i-1][0];        if(bit[i+1]==4 && bit[i]==9)            flag=1;    }    return ans;}int main(){//    freopen("a.txt","r",stdin);//    freopen(".out","w",stdout);    cin>>t;    ini();    while(t--){        cin>>n;        cout<<solve(n+1)<<endl;    }    return 0;}/*DESCRIPTION:最高在16位前i位,最高位为9,不存在49,dp[i][0].....,不存在49,dp[i][1].....,存在49,dp[i][2]dp[1][0]=1dp[1][1]=10dp[1][2]=0dp[i][0]=dp[i-1][1]dp[i][1]=(dp[i-1][1]-dp[i-1][0])*10 + dp[i-1][0]*9 = 10*dp[i-1][1] - dp[i-1][0]dp[i][2]=dp[i-1][0] + dp[i-1][2]*10*/
View Code

hdu3652 dfs写法 含有13且是13的倍数

/*ID: neverchanjePROG:LANG: C++11*/#include<vector>#include<iostream>#include<cstring>#include<string>#include<algorithm>#include<cmath>#include<cstdio>#include<set>#include<queue>#include<map>using namespace std;#define INF 1e9#define maxn#define rep(i,x,y) for(int i=x;i<=y;i++)#define mset(x) memset(x,0,sizeof(x))typedef long long ll;typedef pair<int,int> pii;typedef vector<int> vi;int n;int bit[11];int dp[12][12][3];int dfs(int pos, int mod, int status, bool limit){    if(pos<=0)    return status==2 && mod==0; //含有13,且是13的倍数    if(!limit && dp[pos][mod][status]!=-1)    return dp[pos][mod][status];// 判重    int end=limit?bit[pos]:9, ans=0;    for(int i=0;i<=end;i++){        int nstatus = status;        int nmod = (mod*10+i)%13;        if(status==0 && i==1)            nstatus = 1;        else if(status==1 && i==3)            nstatus = 2;        else if(status==1 && i!=1)            nstatus = 0;        ans+=dfs(pos-1, nmod, nstatus, limit && i==end);    }    if(!limit)    dp[pos][mod][status] = ans;    return ans;}/*6     3     1     3     0   pos对于pos这一位,如果前面一位已经到了6(limit),当前pos这位就只能到3,如果前面一位小于6,当前这位就!limitstatus=0 不含13, 末位不是1status=1 不含13, 末位是1status=2 含13其实dfs的写法比递推的写法更具有灵活性,而且不容易写错当!limit时,pos位之后的dp[pos][mod][status]已经被求出,则把这个值保存下来,防止重复计算*/int solve(int x){    mset(bit);    int len=0;    while(x){        bit[++len] = x%10;        x/=10;    }    memset(dp,-1,sizeof(dp));    return dfs(len, 0, 0, 1);}int main(){    freopen("a.txt","r",stdin);//    freopen(".out","w",stdout);    while(cin>>n){        cout<<solve(n+1)<<endl;    }    return 0;}/*DESCRIPTION:余数为j不存在13,以3为最高位    dp[i][j][0]不存在13    dp[i][j][1]存在13 dp[i][j][2]dp[i][ (dp[i-1][j][1]+3*md[i-1])%13 ][0] += dp[i-1][j][1]dp[i][ (dp[i-1][j][0]+k*md[i-1])%13 ][1] += dp[i-1][j][1]   k=0,1,...9dp[i][ (dp[i-1][j][0]+k*md[i-1])%13 ][1] -= dp[i-1][j][0]dp[i][ (dp[i-1][j][0]+md[i-1])%13 ][2] += dp[i-1][j][0]dp[i][ (dp[i-1][j][2]+k*md[i-1])%13 ][2] += dp[i-1][j][2]    k=0,1...9*/
View Code

 

几道数位dp