首页 > 代码库 > hdu4906 Our happy ending,状态压缩DP
hdu4906 Our happy ending,状态压缩DP
题意:
给一个n个数的数列,从中取一些数构成新数列,
如果新数列中有一些数的和是k,那么这就是一个好数列,问这样的数列的个数。
n,k<=20, a[i] <=L
状态:dp[][state] 中state的二进制每一位表示和为(1~k),1表示可以取到,0表示取不到。
状态转移方程:dp[i][state] = sum(dp[i-1][state‘]); state = 1<<(p-1) || state‘ || ((state‘<<p) &SIZE) ; 1<=p<=min(k,L); //SIZE=(1<<k)-1;
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const LL mod = 1e9 + 7; LL dp[1<<22]; int main() { int t, n, k, L; scanf("%d",&t); while(t--) { scanf("%d%d%d", &n, &k, &L); int MIN = min(L, k); int SIZE = (1<<k)-1; memset(dp, 0, sizeof dp ); dp[0] = 1; for(int i=0; i<n; ++i) { for(int j=SIZE; j>=0; --j) if(dp[j]>0) { LL tmp = dp[j]; for(int p=1; p<=MIN; ++p) { int next=(1<<(p-1))|j|((j<<p)&SIZE); //加上p本身这个数 + 原来可取到的数 + 原来可取到的数加上p之后的数,即组成了所有加上p之后的情况 dp[next] =dp[next] + tmp; if(dp[next]>mod) dp[next] -= mod; } if(k<L)//第i个数选大于k的数 { dp[j] = dp[j] + (LL)tmp*(L-k); if(dp[j]>mod) dp[j] -= mod; } } } LL ans = 0; for(int i=0; i<=SIZE; ++i) if(i&(1<<(k-1))) { ans = ans + dp[i]; if(ans>mod) ans -= mod; } printf("%I64d\n", ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。