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)

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <queue>

 #include <stack>

 #include <vector>

 #include <map>

 #include <set>

 #include <functional>

 #include <time.h>

 using namespace std;

 typedef __int64 ll;

 const int INF = <<;

 const int MAXN = ;

 const ll MOD = (ll) 1e9+;

 ll dp[<<MAXN];

 int n, k, L;

 void solve() {

     memset(dp, , sizeof(dp));

     int MIN = min(L, k);

     int FULL = (<<(k+))-; //全集

     dp[] = ;

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

         for (int S = FULL; S > ; S--) if (dp[S]>) {

             ll tmp = dp[S];

             for (int j = ; j <= MIN; j++)  //枚举每一个有效数字

                 dp[FULL&(S|(S<<j))] = (dp[FULL&(S|(S<<j))]+tmp)%MOD;

             if (MIN<L)

                 dp[S] = (dp[S]+((L-MIN)*tmp)%MOD)%MOD;

         }

     }

     ll ans = ;

     for (int S = ; S <= FULL; S++) if (S&(<<(k)))

         ans = (ans+dp[S])%MOD;

     printf("%I64d\n", ans);

 }

 int main() {

     #ifdef Phantom01

         freopen("HDU4906.txt", "r", stdin);

     #endif //Phantom01

     int T;

     scanf("%d", &T);

     while (T--) {

         scanf("%d%d%d", &n, &k, &L);

         solve();

     }

     return ;

 }

巴特西

HDU 4906 Our happy ending

最新文章

热门文章