转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526
by---cxlove
题目:有N个机器,每天选出R个机器,而且每两个机器的编号差要大于等于K,而且每天将R个机器最多分为M组工作,问最多有多少种方案。
http://acm.hdu.edu.cn/showproblem.php?pid=4045
这个问题分为两个部分,首先是从N个机器中选出R个满足条件的机器有多少种。然后将R个机器最多分为M组有多少种,显然最后为二者的乘积
记得当时比赛的时候解决了第一部分,不记得当时怎么做的,估计是半暴力。。。
首先每两个机器之前至少有K-1个间隔,那么如果还剩余一些位置,则把这些多余的插入到R个机器中。
那么剩余位置便是N-((R-1)*K+1),对于R个机器,R+1个位置,接下来便是把N-((R-1)*K+1)分为R+1个集合,而且可以为空。做法是添加R+1个物品,然后用插板法,这样保证 每一个集合都至少有一个,然后再把每一个集合都减掉一个便是结果,最终结果便是C[N-((R-1)*K+1)+R+1-1][R]。应该比较好理解了。。。。。。
第二部分:将R个元素最多分为M个集合,不为空的方案法。
对于R个元素分为i个集合结果是第二类斯特林数,然后再统计合计一下就OK了
当时跪舔的题目啊。。。。好忧桑
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#define LL long long
#define eps 1e-7
#define MOD 1000000007
using namespace std;
int c[2001][2001]={1},stir2[1005][1005]={1};
int main(){
for(int i=1;i<=2000;i++){
c[i][0]=c[i][i]=1;
for(int j=1;j<i;j++)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%MOD;
}
for(int i=1;i<=1000;i++){
stir2[i][0]=0;
stir2[i][i]=1;
for(int j=1;j<i;j++)
stir2[i][j]=((LL)j*stir2[i-1][j]+stir2[i-1][j-1])%MOD;
}
int n,r,k,m;
while(cin>>n>>r>>k>>m){
int sum=0;
if(n-((r-1)*k+1)<0){
cout<<0<<endl;
continue;
}
for(int i=1;i<=min(r,m);i++)
sum=(sum+stir2[r][i])%MOD;
cout<<((LL)c[n-((r-1)*k+1)+r+1-1][r]*sum)%MOD<<endl;
}
return 0;
}
分享到:
相关推荐
杭电ACMhdu1163
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu1001解题报告
HDU1059的代码
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
杭电ACM课件2014版之(HDUACM201403版_11)特殊的数
hdu2101AC代码
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
在webDIY 和DIY中总结的专题训练
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
自己做的HDU ACM已经AC的题目
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_...
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
hdu题目分类