【DP】【2012 ACM/ICPC 成都赛区现场赛】【I.Count】

【题目来源】http://acm.hdu.edu.cn/showproblem.php?pid=4472

【题目解析】F[I][J]表示的是前I个人，最后一层有J个人的方案数。F[I][J] = Sum{F[I-J][K]} (K为J的约数),意思是枚举前一层的人数，但要注意的是，前一层的人数必须是后一层人数的约数。另外一件值得注意的事是，只有一个headman，所以边界应该设为F[1][1] = 1。最后Ans[I] = Sum{F[I][J]} (1<=J<=I)。貌似是难度最小的一题了，详细看题解。

【代码如下】

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 
 5 //#define FILE_IO
 6 
 7 using namespace std;
 8 
 9 const int Max = 1001, Mod = 1e9 + 7;
10 int N, F[Max][Max], Ans[Max], Cnt;
11 
12 void Prework()
13 {
14     F[1][1] = 1;
15     for (int i = 1; i <= 1000; ++i)
16         for (int j = 1; j <= i; ++j)
17         {
18             for (int k = 1; k <= sqrt(j); ++k)
19             {
20                 if (j % k) continue;
21                 if (k <= i - j) F[i][j] = (F[i][j] + F[i - j][k]) % Mod;
22                 if (k == j / k) continue;
23                 if (j / k <= i - j) F[i][j] = (F[i][j] + F[i - j][j / k]) % Mod;
24             }
25         }
26     for (int i = 1; i <= 1000; ++i)
27         for (int j = 1; j <= i; ++j)
28             Ans[i] = (Ans[i] + F[i][j]) % Mod;
29 }
30 
31 int main()
32 {
33     #ifdef FILE_IO
34     freopen("test.in", "r", stdin);
35     #endif // FILE_IO
36     Prework();
37     while (cin >> N) cout << "Case " << ++Cnt << ": " << Ans[N] << endl;
38     return 0;
39 }