hdu 2089 入手数位dp问题

数位dp解决的问题是指求在一段数的区间里面满足条件的数的个数

核心为两点

http://wenku.baidu.com/link?url=tpfIYzhx_MzevpIM58UZ66pr-87MCFPKTMKFdGDi5jUqyO9ckti0mY6diSz2PZEL_ZBhd2zIbhus1mnzDiAO1B5K2Vu38YDsqjmOvYKFT6q

我自己总结下吧

第一是dp的状态转移方程

dp[i][j] 表示的是以j开头的i位数满足条件的个数为多少

既然是要记录满足条件的个那么 dp[i][j]=sum(dp[i-1][0~9]) 这个不难理解

for(int i=1;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];

                }

            }

        }

然后就是solve函数问题 solve（i）这个函数的作用是求出【0，i）区间满足条件的数的个数

大致的思想是从高位开始逐一枚举比该为数小的数在满足的条件的情况下统计和每次枚举完

举完一位以后 由于是列举比n小的数 所以 每一位枚举结束后 就需要将这个位定下来

花了不少时间入门。。继续干！

#include<cstdio>

#include<iostream>

#include<string.h>

using namespace std;

int dp[][];

int solve(int n)

{

    int dig[],len=;

    memset(dig,,sizeof(dig));

    while(n>)

    {

        dig[++len]=n%;

        n=n/;

    }

    dig[len+]=;

    int ans=;

    for(int i=len;i;i--)//这里的思想 从最高位开始枚举 枚举完一位以后 由于是列举比n小的数 所以 每一位枚举结束后 就需要将这个位定下来

    {

        for(int j=;j<dig[i];j++)

        {

            if(j!=&&!(dig[i+]==&&j==))//判断此时的枚举是否合法

            ans+=dp[i][j];

        }

        if(dig[i]==||(dig[i+]==&&dig[i]==)) break;//之前位置定好了 如果出现了不满足条件的情况 后面继续下去就没有什么意思了

    }

    return ans;

}

int main()

{

    int n,m;

    while(cin>>n>>m)

    {

        if(m+n==) break;

        memset(dp,,sizeof(dp));

        dp[][]=;

        for(int i=;i<=;i++)

        {

            for(int j=;j<=;j++)

            {

                for(int k=;k<=;k++)

                {

                    if(j!=&&!(j==&&k==)) dp[i][j]+=dp[i-][k];

                }

            }

        }

        cout<<solve(m+)-solve(n)<<endl;// 这里要不要加1是要考虑区间的开闭情况

    }

    return;

}

巴特西

hdu 2089 入手数位dp问题

最新文章

热门文章