首页 > 代码库 > hdu4906 Our happy ending --- 状压dp
hdu4906 Our happy ending --- 状压dp
给一个n个数的数列,从中取一些数构成新数列,
如果新数列中有一些数的和是k,那么这就是一个好数列,问这样的数列的个数。
从1~n位枚举其取值从1~min(l,k),来更新可达状态。
dp[i]中i的二进制每一位表示和(1~k),1表示可以取到,0表示取不到。
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f #define eps 1e-6 #define ll long long const ll mod=1e9+7; const int maxn=(1<<21); using namespace std; ll dp[maxn],ans,v; int n,k,l,d,s; int main() { int icy,i,j,p,next; scanf("%d",&icy); while(icy--) { scanf("%d%d%d",&n,&k,&l); d=abs(l-k); l=min(l,k); s=(1<<k)-1; memset(dp,0,sizeof dp); dp[0]=1; for(i=0;i<n;i++) { for(j=s;j>=0;j--) { v=dp[j]; if(v==0) continue; for(p=1;p<=l;p++) { next=(1<<(p-1))|j|((j<<p)&s);//加上p本身这个数 以及 其余所有1的位加上p之后的数 即组成了所有加上p之后的情况 dp[next]=(dp[next]+v)%mod; } dp[j]+=(v*d%mod);//另外此位还可以取不在[1,k]范围内的数,乘起来就行了 dp[j]%=mod; } } ans=0; for(i=0;i<=s;i++) { if(i&(1<<(k-1))) { ans+=dp[i]; ans%=mod; } } cout<<ans<<endl; } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。