首页 > 代码库 > 湖南国庆模拟赛day1 分组
湖南国庆模拟赛day1 分组
题目大意:
给你一个n个数的数列s,要对这些数进行分组,当有任意两个数在一种方案在一起而在另一种方案中不在一起算是两种不同的方案,一个组的“不和谐程度”为组内数的极差,如果只有一个人的话,此组的不和谐程度为0,求有多少种分组方式,使所有组的不和谐程度不超过k?
数据范围
1<=n<=200,0<=k<=1000,1<=si<=500
样例
input1
4 5
1 3 5 7
output1
9
input2
5 6
1 4 5 8 9
output2
20
/*排序,设状态为i,j,k,分别表示前i个数还有j组未充满,不和谐程度为k的方案数,分四种情况讨论:这个数自成一组、这个数为最小值开一个2个数以上的组,把这个数填到别的组中去,把这个数作为最大值填到别的组中去,如果单纯计算k,那么复杂度o(n^2*sumk),显然超时,可以用差分的办法去处理这个极差,这样复杂度o(n^2*k)*/#include<iostream>#include<cstdio>#include<string>#include<cstring>#include<algorithm>#define ll long longusing namespace std;const int mod = 1000000007;const int maxn = 205,maxm = 1005;ll n,m,s[maxn],f[2][maxn][maxm],cur;int read(){ char ch=getchar(); int x=0,f=1; 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 main(){ n = read(); m = read(); for(int i = 1;i <= n;i++)s[i] = read(); sort(s+1,s+1+n); f[0][0][0] = f[0][1][0] = 1; ll tv = 0,tk = 0; for(int i = 2;i <= n;i++){ for(int j = 0;j <= n;j++){ for(int k = 0;k <= m;k++){ tv = f[cur][j][k]; f[cur][j][k] = 0; if(!tv) continue; tk = (s[i]-s[i-1])*j + k; if(tk > m) continue; f[cur^1][j][tk] = (f[cur^1][j][tk] + tv) % mod; f[cur^1][j+1][tk] = (f[cur^1][j+1][tk] + tv) % mod; if(j) f[cur^1][j-1][tk] = (f[cur^1][j-1][tk] + (tv * j) % mod) % mod; f[cur^1][j][tk] = (f[cur^1][j][tk] + (tv * j) % mod) % mod; } } cur ^= 1; } ll ans = 0; for(int i = 0;i <= m;i++) ans = (ans + f[cur][0][i]) % mod; cout<<ans; return 0;}
湖南国庆模拟赛day1 分组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。