51nod p1201 整数划分

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

将N分为若干个不同整数的和，有多少种不同的划分方式，例如：n = 6，{6} {1,5} {2,4} {1,2,3}，共4种。由于数据较大，输出Mod 10^9 + 7的结果即可。

Input

输入1个数N(1 <= N <= 50000)。

Output

输出划分的数量Mod 10^9 + 7。

Input示例

Output示例

4

分析：这题关键在于不同的整数
一个包含数字最多的划分必定是1+2+3+....+m == n
这样(m + 1) * m <= 2 * n
可以确定m是O(sqrt(n))级别的
想到这里很容易想到用dp[i][j]表示I这个数分成j的数组成的划分有多少种。
方程为：dp[i][j] = dp[i - j][j] + dp[i - j][j - 1]
前者表示将i - j划分为j个数，每个数加1就是i划分为j个数的方案了。
但是前者这样有i-j的方案+1形成i分为j个数的方案是不完全的，因为没有1
后者则补充了这部分的答案，表示i-j划分为j个数，每个数+1，并且方案再加入一个1这个元素。
由于数不重复，所以1的个数只能为1个。

仍然用java写这些简单的题目。

 package p1201;

 import java.util.*;

 import java.io.*;

 public class Main

 {

     /**

      * @param args

      */

     final static int MOD = (int) 1e9 + 7;

     public static void main(String[] args)

     {

         // TODO Auto-generated method stub

         Scanner reader = new Scanner(System.in);

         PrintWriter writer = new PrintWriter(System.out);

         int n = reader.nextInt();

         int m = 0;

         while((1 + m) * m / 2 < n) m++;

         int [][] dp = new int[n + 1][m + 1];

         dp[0][0] = 1;

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

             for(int j = (1 + i) * i / 2; j <= n; j++)

             {

                 dp[j][i] = (dp[j - i][i] + dp[j - i][i - 1]) % MOD;

             }

         int ans = 0;

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

             ans = (ans + dp[n][i]) % MOD;

         writer.println(ans);

         reader.close();

         writer.flush();

     }

 }

巴特西

51nod p1201 整数划分

最新文章

热门文章