（切）糕（动归）
（切）糕（动归）
一个集合的价值为其中的最大数减去最小数。给定n个数，请问有多少种划分集合的方案，使得集合的总价值小于k？
我们先把所有元素排好序。由于一个数必须被选，我们可以定义状态\(f[i][j][k]\)，表示选到第i个数，未结束集合数为j，集合总价值为k的方案数。由于一个数可以开启一个集合，关闭一个集合，中继当前的任何一个集合，也可以独占一个集合，因此一共有四种转移：\(f[i][j][k]=\begin{aligned} f[i-1][j-1][k-(a[i]-a[i-1])*(j-1)] \\ +f[i-1][j][k-(a[i]-a[i-1])*j]*j \\ +f[i-1][j+1][k-(a[i]-a[i-1])*(j+1)]*(j+1) \\ +f[i-1][j][k-(a[i]-a[i-1])*j] \end{aligned}\)
似乎这是一种集合计数题的常见套路呢……
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL maxn=205, maxk=1005, mod=1e9+7;
LL f[maxn][maxn][maxk];
LL a[maxn], n, K;
void up(LL i1, LL j1, LL k1, LL i2, LL j2, LL k2, LL x){
if (i2<0||j2<0||k2<0) return;
f[i1][j1][k1]+=f[i2][j2][k2]*x; f[i1][j1][k1]%=mod;
}
int main(){
scanf("%lld%lld", &n, &K);
for (LL i=1; i<=n; ++i) scanf("%lld", &a[i]);
sort(a+1, a+n+1);
f[0][0][0]=1;
for (LL i=1; i<=n; ++i)
for (LL j=0; j<=n; ++j)
for (LL k=0; k<=K; ++k){
up(i,j,k,i-1,j-1,k-(a[i]-a[i-1])*(j-1),1);
up(i,j,k,i-1,j,k-(a[i]-a[i-1])*j,j);
up(i,j,k,i-1,j,k-(a[i]-a[i-1])*j,1);
up(i,j,k,i-1,j+1,k-(a[i]-a[i-1])*(j+1),j+1);
} LL ans=0;
for (LL k=0; k<=K; ++k) ans+=f[n][0][k], ans%=mod;
printf("%lld\n", ans);
return 0;
}安拉胡阿克巴！
1、TDM-GCC是从mingw-w64项目patch而来，全部使用静态链接，对线程不需要额外的DLL，默认使用SJLJ异常（真是好东西）
2、查找与排序——快速排序
3、Django搭建博客后台
4、循序渐进Python3（十）-- 0 -- RabbitMQ
5、模块化编程实例（一）