题解:P7519
gyh20
2021-04-15 23:05:13
来一个 naive 的做法。
首先考虑 $n!$ 级别的做法,考虑枚举一种排列,然后检验是否合法。
具体的,我们发现,如果 $m$ 道题没有分完,可以直接分给最后一个人,也就是说,我们可以依次贪心的给每个人最少的题,使得比其他所有人都高,时间复杂度 $O(n!\times n)$ 。
我们发现,除了第一个人以外,其他所有人只要满足比前一个人高即可,第一个人要比其他所有人都高,于是可以做到 $O(n!)$,但似乎区别不大。
我们发现,$m$ 很小,除 $1$ 外 $b_i$ 只与且最终的 $b_{i-1}$ 和 $a_{i-1}$ 有关,排列中 $b_i=max(b_{i-1},a_{i-1}+b_{i-1}-a_i)$,换句话说,每当 $b_{i-1}$ 增加 $1$,$b_i$ 一定增加 $1$。
这提示我们,可以直接上 Meet-in-Middle,枚举后一半,再枚举前一半合并,假设前一半的最后一个 $b$ 是 $x$,相当于后面所有数的 $b$ 都要加上 $x$。
暴力前缀和的总复杂度是 $O(A_{n}^{(n+1)/2}\times n+2^n\times n\times m)$。
如果你用树状数组维护前缀和可以做到 $O(A_{n}^{(n+1)/2}\times n\times \log m)$,在这道题不优。~~但 $m$ 可以出的更大~~
```cpp
#include<bits/stdc++.h>
using namespace std;
int read(){
int t=0;char v=getchar();
while(v<'0')v=getchar();
while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
return t;
}
int n,p[15],a[15],m,b[15],LMT,f[8195][15][502];
bool v[15];
long long ans;
void dfs(int x,int y){
if(x==LMT+1){
int zt=0;
for(int i=1;i<x;++i)zt|=(1<<p[i]-1);
++f[zt][p[1]][y];
return;
}
int mx=-1;
for(int i=1;i<=n;++i)
if(!v[i]){
int dlt=a[p[x-1]]+b[x-1]-a[i];
if(p[x-1]<i)++dlt;
mx=max(mx,a[i]);
if(dlt<b[x-1])dlt=b[x-1];
if(y+dlt>m)continue;
b[x]=dlt,p[x]=i,v[i]=1,dfs(x+1,y+dlt),v[i]=0;
}
}
void dfs1(int x,int y){
if(x==LMT+1){
int zt=0,B=(1<<n)-1;
for(int i=1;i<x;++i)zt|=(1<<p[i]-1);
B^=zt;
for(int i=1;i<=n;++i)
if(B&(1<<(i-1))){
int dlt=a[p[x-1]]+b[x-1]-a[i];
if(p[x-1]<i)++dlt;
if(dlt<b[x-1])dlt=b[x-1];
dlt=max(dlt,0);
int ss=dlt*(n-LMT)+y;
if(ss<=m)ans+=f[B][i][m-ss];
}
return;
}
int mx=-1;
for(int i=1;i<=n;++i)
if(!v[i]){
int dlt=a[p[x-1]]+b[x-1]-a[i];
if(p[x-1]<i)++dlt;
if(x==1){dlt=max(dlt,mx-a[i]+1);for(int j=i+1;j<=n;++j)if(!v[j])dlt=max(dlt,a[j]-a[i]);}
mx=max(mx,a[i]);
if(dlt<b[x-1])dlt=b[x-1];
if(y+dlt>m)continue;
b[x]=dlt,p[x]=i,v[i]=1,dfs1(x+1,y+dlt),v[i]=0;
}
}
int main(){
n=read(),m=read(),a[0]=-1e9;
for(int i=1;i<=n;++i)a[i]=read(),p[i]=i;
LMT=n>>1;
dfs(1,0);
for(int i=0;i<(1<<n);++i)for(int j=1;j<=n;++j)for(int k=1;k<=m;++k)f[i][j][k]+=f[i][j][k-1];
LMT=(n+1)>>1;
dfs1(1,0);
printf("%lld",ans);
}
```