程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu2089(數位dp)

hdu2089(數位dp)

編輯：C++入門知識

題意：求區間內不含62和4的數的個數；

解法：數位dp。int dfs(int pos,int pre,bool limit,bool have)，pos表示dp到的數位位置，pre表示前一個數位的數字，limit表示到此時數是否有下降（此位取數字是否受限制的意思），have表示之前是否有62；4的排除是靠在每次枚舉下一位i時不取4即可；每個case的dp值都是一樣的，所以只需要計算一遍。

代碼：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;
int dp[15][12];
int num[20];
int p=0;
int dfs(int pos,int pre,bool limit,bool have)
{
    if(pos==0)
        return !have;
    if(have)
        return 0;
    if(!limit&&dp[pos][pre]!=-1)
        return dp[pos][pre];
    int en=limit?num[pos-1]:9;
    int ans=0;
    for(int i=0; i<=en; i++)
    {
        if(i==4)continue;
        ans+=dfs(pos-1,i,limit&&i==en,(pre==6&&i==2));
    }
    if(!limit)
        return dp[pos][pre]=ans;
    else
        return ans;
}
int getans(int t)
{
    if(t==0)
        return 0;
    p=0;
    while(t)
    {
        num[p++]=t%10;
        t/=10;
    }
    int ans=0;
    for(int i=0; i<=num[p-1]; i++)
    {
        if(i==4)
            continue;
        ans+=dfs(p-1,i,i==num[p-1],0);
    }
    return ans-1;
}

int main()
{
    int l,r;
    memset(dp,-1,sizeof dp);
    while(scanf("%d%d",&l,&r)==2)
    {
        if(r==0&&l==0)
            break;
        cout<