【Codeforces 626F】Group Projects

相关链接

题目传送门:http://codeforces.com/problemset/problem/626/F
中文题面:http://h0rnet.hatenablog.com/entry/2016/11/12/CFR_626_F__Group_Projects_(DP)

解题报告

考虑把每个人放到值域上
于是问题转化为搞一些线段,使得总长度之和小于K

考虑每一个节点的决策:
1. 成为线段左端点
2. 成为线段右端点
3. 放到某个线段中间/自己一组

于是我们就有了一个$DP$:
$f[i][j][k]$表示已经处理完前i个数,还有j各线段左端点未配对,线段总长为k的方案数
转移如上文所述,是$O(3)$的
于是复杂度为$O(k*n^2)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;

int f[2][200+9][1000+9],n,arr[1000+9],w,p,k,cnt[500+9],tot,que[1000+9];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main() {
	n = read(); k = read(); w = 1, p = 0;
	for (int i=1;i<=n;i++) cnt[arr[i]=read()]++;
	for (int i=1;i<=500;i++) {
		if (cnt[i]) {
			que[++tot] = i; 
			cnt[tot] = cnt[i];
		}
	}
	que[0] = que[1];
	
	f[p][0][k] = 1;
	for (int i=1,delta;i<=tot;i++) {
		memset(f[w],0,sizeof(f[w]));
		delta = que[i] - que[i-1];
		for (int j=0;j<=n;j++) {
			for (int t=j*delta;t<=k;t++) {
				f[w][j][t-j*delta] += f[p][j][t];
			}
		}
		swap(w, p);
		
		for (int x=1;x<=cnt[i];x++,w^=1,p^=1) {
			memset(f[w],0,sizeof(f[w]));	
			for (int j=0;j<=n;j++) {
				for (int t=0;t<=k;t++) {
					if (f[p][j][t]) {
						LL tmp = f[p][j][t];
						(f[w][j][t] += tmp * (j + 1) % MOD) %= MOD;
						if (j) (f[w][j-1][t] += tmp * j % MOD) %= MOD;
						(f[w][j+1][t] += tmp) %= MOD;				
					}
				}
			}
		}
	}
	int ret = 0;
	for (int i=0;i<=k;i++) 
		ret = (ret + f[p][0][i]) % MOD;
	printf("%d\n",ret);
	return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *