分组

DP

---

题面

有一含$n$个数的数列$\{s\}$，询问各组内极差（$max-min$)之和小于等于$k$的分组方案数。

• $20pts\ n\leq10$
• $35pts\ k\leq2$
• $50pts$ $s_i$只有两取值
• $80pts\ \sum s_i\leq1000$
• $100pts\ n\leq200,k\leq1000,1\leq s_i\leq500$

解析

$20pts$算法

每加入一个数，只有两种方案：新建组$or$加入已有组
以此$DFS$暴力枚举每一种方案。

$35pts$算法

预处理$n$个相同数字分为$m$组的方案数$dp[n][m]$。
方程为

$$dp[i][j]=dp[i-1][j-1]+dp[i-1][j]*j$$
枚举极差不为$0$的组，其它只能同类数字为一组，统计即可。
实现起来似乎有难度。

$50pts$算法

枚举两种数的分组情况，再枚举包含两种数的组数（通过将两方各一组合并来实现），用组合数计算。

$80pts$算法

看到方案数就想想怎么$DP$。
一开始想设$f[i][j]$表示前$1-i$小数，分组后形成极差和为$j$的方案数。
但这样很不好转移，加入一个数后，如果该数单独成组，则不影响极差；如果进入已有组，则影响极差。
再因，如点进入已有组，统计方案数需要当前未关闭组数，我们需要加一维状态：当前未关闭组数。
则设$f[i][j][k]$。

一个数字有$4$种转移：单独作为一组、新建一个还需填数的组 (代价和$−s_i$ 、填入一个已有的组 (不作为最大值)、填入一个已有的组并作为最大值(不再需要填数,代价和$+s_i$)。
如此，则极差和正可达$\sum s_i$，负可达$-\sum s_i$。
复杂度$O(n^2\sum s_i)$

$100pts$算法

复杂度瓶颈是$\sum s_i$。
没感到极差和为负是一个很怪异且不太好表示的事情吗？
从另一个角度想，每当我们加入一个数，现存所有未关闭组（$j$个）的极差都将加上$a[i+1]-a[i]$，极差和增加$(a[i+1]-a[i])*j$。
极差和超过$k$就可以停止了。
复杂度降到$O(n^2k)$。
而且空间开不下，我们需要滚动（最大特点就是当前数组传完值后要清$0$）。。。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=250,mod=1e9+7;
int n,k,a[N],id[N],mn[N],mx[N],tong[N<<2],mxx;
ll ans,dp[2][N][2500],lim;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void ok(re ll &x){while(x>=mod) x-=mod;}
int main()
{
  n=gi();lim=gi();
  fp(i,1,n) a[i]=gi(),mxx=max(mxx,a[i]);
  sort(a+1,a+1+n);
  re int now=0,nxt=1;
  dp[now][1][0]=dp[now][0][0]=1;
  fp(i,1,n-1)
  {
    fp(j,0,n)
    fp(k,0,lim)
    {
      re ll t=dp[now][j][k],w=k+(a[i+1]-a[i])*j,p=t*j;
      ok(p);dp[now][j][k]=0;
      if(w>lim) continue;ok(w);
      ok(dp[nxt][j][w]+=t);
      if(j) ok(dp[nxt][j-1][w]+=p);
      ok(dp[nxt][j+1][w]+=t);
      ok(dp[nxt][j][w]+=p);
    }
    swap(now,nxt);
  }
  fp(i,0,lim) ok(ans+=dp[now][0][i]);
  printf("%lld\n",ans);
  fclose(stdin);
  fclose(stdout);
  return 0;
}