相关链接
题目传送门: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; }