AC日记——幸运号码 51nod 1043

幸运号码

思路：

　　传说中的数位dp；

　　不难发现，n(n<1000) ，那么，n个数的最大和为9*1000=9000；

　　对于9000*1000的时间范围，我们可以用dp来解决；

　　dp[i][j]，表示第i为数总和为j的号码的个数；

　　每个dp[i][j]都是dp[i-1][j-v](0<=v<=9) 的总和；

　　然后按照左边的n和右边的n，分为有前导0，和没有前导0进行dp；

　　然后输出排列的答案即可；

　　dp[1000][9000]*2会爆空间，所以我选择压掉i维；

来，上代码：

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

#define ri 9005

#define mod 1000000007

long long n,dp[],ans,f[];

int main()

{

    scanf("%d",&n),f[]=;

    for(int i=;i<=;i++) dp[i]=,f[i]=;

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

    {

        for(int j=*n;j>=;j--)

        {

            long long dpos=,fpos=;

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

            {

                if(j-v>=)

                {

                    fpos=(fpos+f[j-v])%mod;

                    dpos=(dp[j-v]+dpos)%mod;

                }

                else break;

            }

            f[j]=fpos,dp[j]=dpos;

        }

    }

    for(int i=;i<=*n;i++) ans=(ans+(dp[i]*f[i])%mod)%mod;

    cout<<ans;

    return ;

}

巴特西

AC日记——幸运号码 51nod 1043

最新文章

热门文章