Mountain Number FZU-2109數位dp

Mountain NumberFZU-2109

　　題目大意：一個大于0的數字x，分寫成x=a[0]a[1]a[2][3]..a[n]的形式，（比如x=1234,a[0]=1,a[1]=2,a[3]=3,a[3]=4）,Mountain Number要滿足對于a[2*i+1]要大于等于a[2*i]和a[2*i+2]，給定范圍l,r問，有多少個Mountain Number

　　就簡單的數位dp，照著題意寫就行，而且求的是數字，前導0并沒有任何影響，對于全0的情況，我們把0也特別視為Mountain Number,也就消除了全0的影響。然后就根據奇偶性判斷，奇數位的數要大于等于前一個，偶數位的數要小于等于前一個的數。

　　一開始看錯題意了，以為要滿足a[0]<=a[1]>=a[2],a[1]<=a[2]>=a[3]，那么就是a[0]<=a[1]=a[2]=a[3]=..>=a[n]，然后寫著寫著把自己寫暈了，仔細看題目才發現，只是對奇數位的數要大于等于前后的數。

#include<cstdio>
int a[36],dp[36][10][2];//dp[i][j][k]第i數位的前一個數是j奇偶性是k的答案 
int dfs(int p,int pre,bool jo,bool lim)
{
    if(p<0)
        return 1;
    if(!lim&&dp[p][pre][jo]!=-1)
        return dp[p][pre][jo];
    int up=(lim ? a[p] : 9),ans=0;
    for(int i=0;i<=up;i++)
    {
        if(!jo&&i<=pre)
            ans+=dfs(p-1,i,1,lim&&i==a[p]);
        else if(jo&&i>=pre)
            ans+=dfs(p-1,i,0,lim&&i==a[p]);
    }
    if(!lim)
        dp[p][pre][jo]=ans;
    return ans;
}
int solve(int x)
{
    int n=0;
    while(x)
    {
        a[n++]=x%10;
        x/=10;
    }
    return dfs(n-1,9,0,1);
}
int main()
{
    int t,l,r;
    for(int i=0;i<=32;i++)
        for(int j=0;j<=9;j++)
            for(int k=0;k<2;k++)
                dp[i][j][k]=-1;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",solve(r)-solve(l-1)); 
    }
    return 0;
}

?

?