题目描述
有一个序列(A)，你可以随意排列这个序列，设(s=sum_{i=1}^{n-1}|a_i-a_{i+1}|) 。
问你最终(sleq m)的方案数有几种。
保证(A)中的元素两两不同。
(nleq 100,a_i,mleq 1000)
题解
考虑从大到小把(A)中的元素插回去。
插入一个数时考虑的是它的相对位置（相对之前插入的其他数）。
我们把连续的一段数称作山峰，把连续的一段空位称为山谷（一个山谷中空格的个数是不确定的，因为我们只考虑相对位置）。
那么可以DP了。
设(f_{i,j,k,S})为前(i)个数，插入完后有(j)个山谷，和为(k)的方案数。
在中间插入的转移有三种情况（设(1)为山峰，(0)为山谷）：
在山峰和山谷间插入：(01 ightarrow011)；
把一个山谷分成两个：(101->10101)；
填上一个山谷：(101 ightarrow 111)
往边上插的转移类似。
这样就会带来两个问题：
和可能会加到很大在减下来。所以我们在DP到第(i)层时设第(i)层为地平面来计算排列的(s)值。转移时(s)要加上山谷的个数( imes 2+2)（还有两边）。
最左端和最右端的贡献很难计算。这就是状态中(S)的用处了。(S)表示确定了那些端点，如果一个端点被确定下来转移时就不会有贡献了。
时间复杂度：(O(n^2m))
当然，状态可以再减小一些（也是常数级的），但我懒得改了。
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long ll;
const ll p=1000000007;
ll f[2][2][110][1010];
ll g[2][2][110][1010];
int a[110];
int n,m;
void add(ll &a,ll b)
{
a=(a+b)%p;
}
void gao(int v)
{
memset(f,0,sizeof f);
int j,k;
for(j=0;j<=n/2+1;j++)
for(k=0;k<=m;k++)
{
if(k+(2*j+2)*v<=m)
add(f[0][0][j][k+(2*j+2)*v],g[0][0][j][k]);
if(k+(2*j+1)*v<=m)
{
add(f[0][1][j][k+(2*j+1)*v],g[0][1][j][k]);
add(f[1][0][j][k+(2*j+1)*v],g[1][0][j][k]);
}
if(k+2*j*v<=m)
add(f[1][1][j][k+2*j*v],g[1][1][j][k]);
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
int i,j,k;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());
for(i=1;i<n;i++)
a[i]-=a[i+1];
g[0][0][0][0]=1;
g[0][1][0][0]=1;
g[1][0][0][0]=1;
g[1][1][0][0]=1;
gao(a[1]);
for(i=2;i<=n;i++)
{
memset(g,0,sizeof g);
for(j=0;j<=n/2+1;j++)
for(k=0;k<=m;k++)
{
if(j)
{
//往中间放 开一个新的1
add(g[0][0][j+1][k],j*f[0][0][j][k]);
add(g[0][1][j+1][k],j*f[0][1][j][k]);
add(g[1][0][j+1][k],j*f[1][0][j][k]);
add(g[1][1][j+1][k],j*f[1][1][j][k]);
//往中间放 和1相邻
add(g[0][0][j][k],2*j*f[0][0][j][k]);
add(g[0][1][j][k],2*j*f[0][1][j][k]);
add(g[1][0][j][k],2*j*f[1][0][j][k]);
add(g[1][1][j][k],2*j*f[1][1][j][k]);
//往中间放 填上一个0
add(g[0][0][j-1][k],j*f[0][0][j][k]);
add(g[0][1][j-1][k],j*f[0][1][j][k]);
add(g[1][0][j-1][k],j*f[1][0][j][k]);
add(g[1][1][j-1][k],j*f[1][1][j][k]);
}
//往旁边放
add(g[0][0][j+1][k],2*f[0][0][j][k]);
add(g[0][1][j+1][k],f[0][0][j][k]);
add(g[1][0][j+1][k],f[0][0][j][k]);
add(g[0][0][j][k],2*f[0][0][j][k]);
add(g[0][1][j][k],f[0][0][j][k]);
add(g[1][0][j][k],f[0][0][j][k]);
add(g[0][1][j+1][k],f[0][1][j][k]);
add(g[1][1][j+1][k],f[0][1][j][k]);
add(g[0][1][j][k],f[0][1][j][k]);
add(g[1][1][j][k],f[0][1][j][k]);
add(g[1][0][j+1][k],f[1][0][j][k]);
add(g[1][1][j+1][k],f[1][0][j][k]);
add(g[1][0][j][k],f[1][0][j][k]);
add(g[1][1][j][k],f[1][0][j][k]);
}
gao(a[i]);
}
ll ans=0;
for(i=0;i<=m;i++)
add(ans,f[1][1][0][i]);
printf("%lld
",ans);
return 0;
}