hdu4906 Our happy ending --- 状压dp
浏览数：29 /
时间：2015年06月11日
给一个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;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
