HDU 4906 Our happy ending

题意:

  Given a sequence a_1,a_2,...,a_n, if we can take some of them(each a_i can only be used once), and they sum to k, then we say this sequence is a good sequence.
   How many good sequence are there? Given that each a_i is an integer and 0<= a_i <= L.

  给你一个序列: a_1, a_2, ..., a_n,如果我们能够取出他们中的一些(每个a_i只能取一次),并且他们的和是k,我们就把这个序列称为一个好的序列。

  如果每个a_i都是0到L中的整数,那么他们一共能组成多少好序列呢?

 

思路:

  状态压缩。

  dp[i][S]表示长度为i的序列,能组合成的加和的集合为S的情况有多少种(集合用数字的位来表示,1表示可以组成,0表示不可以。因为有用的数字最多只有20,所以可以这样表示)。

  这样,我们可以枚举第i+1位,得到一个新的可以组成的数的集合。原理和背包类似。 在和别人的讨论中发现,用位运算可以很方便的表示这个背包的内容,我们假设原本可以组成的集合为S,现在枚举放不放进背包的数是j。那么,不放进背包的时候可能组成的集合还是S;而放进背包的话,可能组成的集合就变成了(S<<j);所以枚举j可能组成的所有集合就是 S|(S<<j) 看起来是不是很简洁。

  所以这样,我们的转移方程就可以写成 dp[i+1][S] = sum{dp[i][S0] | (S0|(S0<<j) ) == S}

  值得注意的是,直接开 n*2^n 的数组可能会爆内存,观察转移是一层一层的进行的,所以我们可以用滚动数组进行优化。

(最后,感谢alpc同学的耐心讲解 :)

 

代码:(这样做会跑2秒,真心不知道那些0毫秒的怎么做的Orz)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cmath>
 6 #include <algorithm>
 7 #include <string>
 8 #include <queue>
 9 #include <stack>
10 #include <vector>
11 #include <map>
12 #include <set>
13 #include <functional>
14 #include <time.h>
15 
16 using namespace std;
17 
18 typedef __int64 ll;
19 
20 const int INF = 1<<30;
21 const int MAXN = 21;
22 const ll MOD = (ll) 1e9+7;
23 
24 ll dp[1<<MAXN];
25 int n, k, L;
26 
27 void solve() {
28     memset(dp, 0, sizeof(dp));
29     int MIN = min(L, k);
30     int FULL = (1<<(k+1))-1; //全集
31 
32     dp[1] = 1;
33     for (int i = 0; i < n; i++) {
34         for (int S = FULL; S > 0; S--) if (dp[S]>0) {
35             ll tmp = dp[S];
36             for (int j = 1; j <= MIN; j++)  //枚举每一个有效数字
37                 dp[FULL&(S|(S<<j))] = (dp[FULL&(S|(S<<j))]+tmp)%MOD;
38             if (MIN<L)
39                 dp[S] = (dp[S]+((L-MIN)*tmp)%MOD)%MOD;
40         }
41     }
42 
43     ll ans = 0;
44     for (int S = 1; S <= FULL; S++) if (S&(1<<(k)))
45         ans = (ans+dp[S])%MOD;
46 
47     printf("%I64d\n", ans);
48 }
49 
50 int main() {
51     #ifdef Phantom01
52         freopen("HDU4906.txt", "r", stdin);
53     #endif //Phantom01
54 
55     int T;
56     scanf("%d", &T);
57     while (T--) {
58         scanf("%d%d%d", &n, &k, &L);
59         solve();
60     }
61 
62     return 0;
63 }
View Code

 

HDU 4906 Our happy ending,,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。