「NOIP模拟赛」篮球比赛2
由于Czhou举行了众多NOIP模拟赛，也导致放学后篮球比赛次数急剧增加。神牛们身体素质突飞猛进，并且球技不断精进。这引起了体育老师彩哥的注意，为了给校篮球队找到势均力敌的对手，彩哥找到了Czhou神，想要和机房篮球队进行多场友谊赛。Czhou为了顾全校篮球队面子，决定派出配合默契又不至于吊打校篮球队的阵容。
而机房神牛的能力值受到游戏时长，训练时长，个人基础值得影响，可能会不断变化。所以Czhou想根据神牛当天状态从中选出若干名选手，使他们的能力值和等于k。
Input: basketball2.in
一行三个数n,k,l。表示机房有n个神牛，选出队员能力值和为k，每个神牛的能力最大值<=L且>=0。
Ouput:basketball2.out
输出一个数，表示方案数，方案满足选出若干选手使能力和为k。因为答案比较大，最后模10^9+7。
Sample.in
2 2 2
Sample.out
6
样例说明：神牛的能力值可能为(0,2)(1,2)(1,1)(2,0)(2,1)(2,2)，这样都可以选出一些数字使他们的能力值和为2。
对于（0,2）表示第一只牛能力值为0，第二只牛能力为2
类似的
对于（1,2）选出2即满足要求。
对于（1,1）选出全部选手即满足要求。
所以（0,2）（1，1）都是满足要求的方案。
数据范围：
n,k<=20
0<=L<=10^9.
题解
暴力直接爆搜+背包
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K,l,ans; int a[25]; int f[105]; void solve() { memset(f,0,sizeof(f)); f[0]=1; for(int i=1;i<=n;i++) for(int j=K;j>=0;j--) if(j-a[i]>=0) if(f[j-a[i]])f[j]=1; if(f[K]) ans++; } void dfs(int x) { if(x==n+1){solve();return;} for(int i=0;i<=l;i++) { a[x]=i; dfs(x+1); } } int main() { n=read();K=read();l=read(); dfs(1); printf("%d\n",ans); return 0; } |
正解状压
排列组合以及其余的dp算法似乎都会涉及重复统计的问题
dp[i][state] 表示前i位，state的二进制每一位表示和为（1～k），1表示可以取到，0表示取不到，0<=state<(1<<K)-1
枚举第i+1个取的数 f[i][j]->f[i+1][(i|(i<<x)|(1<<(x-1)))&((1<<K)-1)]
这是一个2^n*n^2的dp，但是状压废状态比较多，剪掉废状态即可AC。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int ans; int n,K,l,ed; int f[25][1048576]; int main() { //freopen("basketball2.in","r",stdin); //freopen("basketball2.out","w",stdout); n=read();K=read();l=read(); ed=(1<<K)-1; for(int i=1;i<=min(l,K);i++) f[1][1<<(i-1)]=1; if(K<=l)f[1][0]=l-K+1; for(int i=1;i<n;i++) { f[i][0]=max(f[i][0],1); for(int j=0;j<=ed;j++) if(f[i][j]) { for(int x=0;x<=min(l,K);x++) { int to=((j<<x)|j|(1<<(x-1)))&ed; f[i+1][to]=(f[i+1][to]+f[i][j])%mod; } if(K<=l)f[i+1][j]=(f[i+1][j]+(ll)f[i][j]*(l-K)%mod)%mod; } } for(int i=0;i<=ed;i++) if(i&(1<<(K-1))) ans=(ans+f[n][i])%mod; printf("%d\n",ans); return 0; } |
OI 课件=>
g