幸运数字（数位dp）

个人心得：数位dp处理起来是真的麻烦，本来动态规划就够头疼的了，菜的一批。

来看这个题目吧，题目在下面。

把题目变成可以求得就是求前n个数中1-n*9的情况的总和，所以用dp【i】【j】，表示前i个数中和为j的个数。

状态转移方程就是

dp[i][j]=dp[i-1][j-k] 0=<k<=9;

但是后面要注意前导为0的情况所以总和ans=(dp[i][j]-dp[i-1][j])*dp[i][j]（后面N段不需要考虑前导为0的情况，前面前导为0的情况就是前n-1位中和为j的值）

脑瓜子还是不行呀！！！数位dp看了基本绕路走。。。。

1个长度为2N的数，如果左边N个数的和 = 右边N个数的和，那么就是一个幸运号码。

例如：99、1230、123312是幸运号码。

给出一个N，求长度为2N的幸运号码的数量。由于数量很大，输出数量 Mod 10^9 + 7的结果即可。

Input

输入N(1<= N <= 1000)

Output

输出幸运号码的数量 Mod 10^9 + 7

Input示例

Output示例

 #include<iostream>

 #include<cstring>

 #include<string>

 #include<cstdio>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const long long mod=;

 long long  dp[][];

 int main()

 {

     memset(dp,,sizeof(dp));

     dp[][]=;

     int i,n;

     cin>>n;

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

         dp[][i]=;

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

     for(int j=;j<=*i;j++){

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

             {

                 if(j>=k)

                 dp[i][j]=(dp[i][j]+dp[i-][j-k])%mod;

             }

     }

     long long ans=;

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

          ans=(ans+dp[n][i]*(dp[n][i]-dp[n-][i]))%mod;

     cout<<ans<<endl;

     return ;

 }

巴特西

幸运数字（数位dp）

最新文章

热门文章