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