HDU 4906 Our happy ending (状压DP)
浏览数：29 /
时间：2015年06月11日
HDU 4906 Our happy ending
题意：给定n个数字，每个数字可以是0-l,要选其中一些数字，然后使得和为k，问方案
思路：状压dp，滚动数组，状态表示第i个数字，能组成的数字状态为s的状态，然后每次一个数字，循环枚举它要选取1 - min(l,k)的多少，然后进行状态转移
代码：
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = (1<<20) + 5;
const ll MOD = 1000000007;
int t, n, k;
ll l, dp[N];
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d%lld", &n, &k, &l);
int s = (1<<k);
ll yu = l - k;
l = k;
memset(dp, 0, sizeof(dp));
dp[0] = 1;
while (n--) {
for (int i = s - 1; i >= 0; i--) {
if (dp[i] == 0) continue;
ll tmp = yu * dp[i] % MOD;
ll now = dp[i];
for (int j = 1; j <= l; j++) {
int next = i|((i<<j)&(s - 1)|(1<<(j - 1)));
dp[next] = (dp[next] + now) % MOD;
}
dp[i] = (dp[i] + tmp) % MOD;
}
}
ll ans = 0;
for (int i = 0; i < s; i++) {
if (i&(1<<(k - 1))) {
ans = (ans + dp[i]) % MOD;
}
}
printf("%lld\n", ans);
}
return 0;
}郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
