首页 > 代码库 > cf414B(dp)

cf414B(dp)

题目链接:http://codeforces.com/problemset/problem/414/B

 

题意:定义所有元素是其前一个元素的倍数的数列为good sequence,给出 n, 和 k,求1....n组成的长度为k的good sequence 的数目;

 

思路:dp

用dp[i][j]存储以 j 结尾长度为 i 的good sequence 的数目,那么我们不难发现dp[i][j]可以由dp[i-1][l] (l | j)求和得到,

即状态转移方程为:dp[i][j] = Σdp[i-1][l] (l | j);

注意我们可以先打表得到1...n的因子,不然可能会tle;

 

代码:

技术分享
 1 #include <bits/stdc++.h>
 2 #define MAXN 2010
 3 #define ll long long
 4 using namespace std;
 5 
 6 const int mod=1e9+7;
 7 ll dp[MAXN][MAXN]; //dp[i][j]表示以j结尾长度为i的good sequence的数目
 8 vector<int>v[MAXN];//v[i]存储i的因子
 9 
10 int main(void){
11     int n, k;
12     cin >> n >> k;
13     for(int i=1; i<=n; i++){
14         dp[1][i]=1;
15     }
16     for(int i=1; i<=n; i++){//求i的因子
17         for(int j=1; j<=i; j++){
18             if(i%j==0){
19                 v[i].push_back(j);
20             }
21         }
22     }
23     for(int i=2; i<=k; i++){
24         for(int j=1; j<=n; j++){
25             for(int k=0; k<v[j].size(); k++){
26                 dp[i][j]=(dp[i][j]+dp[i-1][v[j][k]])%mod;
27             }
28         }
29     }
30     ll ans=0;
31     for(int i=1; i<=n; i++){
32         ans=(ans+dp[k][i])%mod;
33     }
34     cout << ans << endl;
35     return 0;
36 }
View Code

 

cf414B(dp)