P9197 [JOI Open 2016] 摩天大楼
传送门
为了规避绝对值，我们可以先将\(a_i\)从小到大排序
考虑\(DP\)：假如我们计算到\(a_g\)，则\(f_{i,j,0/1,0/1}\)定义为当前阶段有\(i\)段，这\(i\)段数全用\(a_g\)连接的值为\(j\)，是否有左端点，是否有右端点（\(1\)是\(0\)否）
举个例子辅助理解：
枚举到\(a_g\)的\(f_{3,20,1,0}\)为：
\[z_1+|r_1-a_g|+|a_g-l_2|+z_2+|r_2-a_g|+|a_g-l_3|+z_3+|r_3-a_g|=20
\]
其中，\(z_1,z_2,z_3\)分别表示\(1,2,3\)段中的绝对值和，\(r\)表示该组的最右边的值，\(l\)表示该组最左边的值。
因为我们从小到大排序，所以无论在哪里插入\(a_g\)，我们枚举到\(a_g\)时都会增加一个\(a_g-a_{g-1}\)的值，则我们共会增加\(p=(a_g-a_{g-1})\times (2\times j-le-ri)\)。
我们考虑\(a_g\)可以插到哪里，下面是一种分类方式（挺经典的）
\(1\)、仅延续\(z_1,z_2,z_3\)中某一段，成为\(z_1,z_2,z_3\)中的一部分，有\((j\times 2-le-ri)\)种方案
\(2\)、合并\(z_1,z_2,z_3\)中相邻的两段，有\((j-1)\)中方案
\(3\)、成为新一段，有\((j+1-le-ri)\)中方案
\(4\)、成为右端点
\(4.1\)，延续最右边的那段，\(1\)种
\(4.2\)，新开一段，\(1\)种
\(5\)、成为左端点
\(5.1\)，延续最右边的那段，\(1\)种
\(5.2\)，新开一段，\(1\)种
上代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=110,M=1100,mod=1e9+7;
ll n,l,a[N];
ll f[N][M][2][2],g[N][M][2][2];
int main()
{
scanf("%lld %lld",&n,&l);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
sort(a+1,a+n+1);
f[1][0][0][0]=1;
f[1][0][0][1]=1;
f[1][0][1][0]=1;
f[1][0][1][1]=1;
for(ll i=2;i<=n;i++)
{
for(ll le=0;le<=1;le++)
for(ll ri=0;ri<=1;ri++)
for(ll j=1;j<=n;j++)
for(ll k=0;k<=l;k++)
g[j][k][le][ri]=f[j][k][le][ri],f[j][k][le][ri]=0;
//init()
for(ll j=1;j<=n;j++)
for(ll k=0;k<=l;k++)
for(ll le=0;le<=1;le++)
for(ll ri=0;ri<=1;ri++)
{
ll p=(2*j-ri-le)*(a[i]-a[i-1]);
if(p+k>l) continue;
f[j][k+p][le][ri]+=g[j][k][le][ri]*(2*j-le-ri),f[j][k+p][le][ri]%=mod;
if(j!=1) f[j-1][k+p][le][ri]+=g[j][k][le][ri]*(j-1),f[j-1][k+p][le][ri]%=mod;
if(j!=n) f[j+1][k+p][le][ri]+=g[j][k][le][ri]*(j+1-le-ri),f[j+1][k+p][le][ri]%=mod;
if(ri==0)
{
f[j][k+p][le][1]+=g[j][k][le][ri],f[j][k+p][le][1]%=mod;
f[j+1][k+p][le][1]+=g[j][k][le][ri],f[j+1][k+p][le][1]%=mod;
}
if(le==0)
{
f[j][k+p][1][ri]+=g[j][k][le][ri],f[j][k+p][1][ri]%=mod;
f[j+1][k+p][1][ri]+=g[j][k][le][ri],f[j+1][k+p][1][ri]%=mod;
}
}
}
ll ans=0;
for(ll i=0;i<=l;i++)
ans=(ans+f[1][i][1][1])%mod;
printf("%lld\n",ans);
return 0;
}