首页 > 代码库 > hdu2089：不要62（基础数位dp）

hdu2089：不要62（基础数位dp）

2024-07-26 05:16:16   220人阅读

题意：规定一个合法的号码不能含有4或者是连续的62

给定区间[n,m] 问此区间内合法的号码的个数

分析：数位dp

dp[i][j]代表 最高位为 j 的 i 位数有多少个合法的

然后按题目规则进行转移即可

dp结束后，再统计范围内的总数，最后打表输出

代码：

 

#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define MAX 100000000int n,k,m;int ans[1000010];int dp[10][10];int fun(int x){    int t=0;    int res=0;    int a[10];    while(x)    {        a[t++]=x%10;        x/=10;    }    for(int i=t;i;i--)    {        for(int j=0;j<a[i-1];j++)        {            if((!(j==2&&a[i]==6)))                res+=dp[i][j];        }        if((a[i-1]==2&&a[i]==6)||a[i-1]==4)            break;    }    return res;}void DP(){    for(int i=0;i<=9;i++)    {        if(i!=4)            dp[1][i]=1;        else            dp[1][i]=0;    }    for(int i=2;i<=7;i++)    {        for(int j=0;j<=9;j++)        {            for(int k=0;k<=9;k++)            {                if(j!=4&&(j!=6||k!=2))                    dp[i][j]+=dp[i-1][k];            }        }    }}void solve(){    for(int i=1;i<=1000001;i++)    {        ans[i]=fun(i);    }}int main(){    DP();    solve();    while(scanf("%d%d",&n,&m)&&(n+m))    {        printf("%d\n",ans[m+1]-ans[n]);    }    return 0;}

 

hdu2089：不要62（基础数位dp）


联系
我们