HDOJ 4906 Our happy ending 状压DP(数位DP?)

http://acm.hdu.edu.cn/showproblem.php?pid=4906

题意:

N个数的序列,每个数可以选择填0-L,如果一个序列可以选出某些数,他们的和为K,那么这个序列就是”好序列“,给定N<=20,K<=20,0<=L<=10^9,问好序列的个数。

 

分析:

N和K很小,所以要想办法利用这个特性(状压?搜索?)。虽然L很大,但实际上一个数大于K的时候,肯定是不能选他组成K的。我们就先考虑L<=K的做法。

然后还是考虑不出来。。

好吧,看题解吧。。

目前能搜到的题解都写得比较简单,我稍微详细一些?

dp[i][j],j用二进制来表示,第k位为1,说明已有的序列能选出几个数使得和为k,dp[i][j]就表示前i个数的序列能表示j的方案数。

初始dp[0][0]=1,answer是 Σdp[n][j],其中j的第K位为1。

转移的话,逆推有点难想,还是顺推吧,第i+1个数,从0到L,我们分成0,1--K,K+1--L来考虑:

如果第i+1位选择0,那么dp[i][j]可以转移给dp[i+1][j],因为多了个0,能表示的和(j)还是一样。

如果第i+1位选择K+1到L中的数,那么dp[i][j]可以转移给dp[i+1][j],原因同上。

如果第i+1位选择1到K中的数,假设是x,那么dp[i][j]可以转移给dp[i+1][to],to = j|1<<(x-1)|(j<<x)&((1<<K)-1)

(重点)to中的j表示,我们不选择当前这个x能表示的和,1<<(x-1)表示只选择当前这个x能表示的和,最后一项是在之前已经能表示的和上再加上一个x,这些新的和我们都能表示了,同时为了不让他超过最大值,所以再和最大值按位与。

然后像背包一样倒序枚举,就可以省略掉i这一维。

 

代码:

 1 #include<cstdio> 
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int mod = (int)1e9+7;
 7 int T, N, K, L, MAX, extra;
 8 long long dp[(1<<20)+10];
 9 int main()
10 {
11     scanf("%d", &T);
12     while(T--)
13     {
14         scanf("%d%d%d", &N, &K, &L);
15         memset(dp, 0, sizeof(dp));
16         if (L > K){
17             extra = L - K;
18             L = K;
19         }
20         else extra = 0;
21         dp[0] = 1;
22         MAX = (1 << K) - 1;
23         for (int i = 1; i <= N; i++)
24             for (int j = MAX; j >= 0; j--){
25                 if (dp[j] == 0) continue;
26                 long long tmp = dp[j];
27                 for (int k = 1; k <= L; k++){
28                     int to = j | 1<<(k-1) | ((j<<k)&MAX);
29                     dp[to] += tmp;
30                     if (dp[to] >= mod) dp[to] -= mod;
31                 }
32                 //if (dp[j] != tmp) printf("%d %lld %lld\n", j, dp[j], tmp);
33                 dp[j] = (dp[j] + tmp * extra) % mod;
34             }
35         long long ans = 0;
36         for (int i = 1 << (K-1); i <= MAX; i++){
37             ans += dp[i];
38             if (ans >= mod) ans -= mod;
39         }
40         printf("%I64d\n", ans);
41     }
42     return 0;
43 }

 

HDOJ 4906 Our happy ending 状压DP(数位DP?),,5-wow.com

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