【题解】P9197 [JOI Open 2016] 摩天大楼

· · 题解

很套路的一道题。

题目大意

给定长为 n 的序列 a，a_i 互不相同。你要将其重排成 f_1,f_2,\dots,f_n，需要满足 |f_1-f_2|+|f_2-f_3|+\dots+|f_{n-1}-f_n| \leq L，求满足条件的重排方案数，对 10^9+7 取模。

1 \leq n \leq 100,1 \leq L,a_i \leq 1000

题目分析

首先把重排后的序列 f 拍到平面上，横坐标为下标，纵坐标为 f_i，如下图：

那么所要求的就是红线的（纵坐标差）长度和。容易想到从上往下扫，然后动态计算目前的折线长度和：

每次从大到小加入 a_i，那么新增加的折线就有 2 \times 目前连续段数个（下图绿色部分）：

不过注意到当最后一个数已经插入时，后面不能再算贡献（绿色紫色虚线部分），同理，第一个数已经插入时前面不能再算贡献。于是设 dp_{i,j,0/1,0/1} 表示目前已经有 i 个连续段，答案为 j，第一个数/最后一个数有没有被加进去，答案就是 dp_{1,\leq L,1,1}。

转移的话大致有三种：

时间复杂度 \mathcal O(n^2L)，足以通过。

代码

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
using namespace std;
ll n,lim,a[110],f[110][1010][2][2],g[110][1010][2][2],ans=0;
inline void inc(ll &x,ll y){
    ((x+=y)>=mod)?(x-=mod):0;
}
int main(){
    scanf("%lld %lld",&n,&lim);
    fr(i,1,n) scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);//从大到小排序 
    fr(p,0,1) fr(q,0,1) f[1][0][p][q]=1;
    fr(i,2,n){
        fr(j,1,i-1) fr(k,0,lim) fr(p,0,1) fr(q,0,1) g[j][k][p][q]=f[j][k][p][q];
        fr(j,1,i-1) fr(k,0,lim) fr(p,0,1) fr(q,0,1) f[j][k][p][q]=0;
        fr(j,1,i-1){
            fr(k,0,lim){
                fr(p,0,1){
                    fr(q,0,1){
                        if(!g[j][k][p][q]) continue;
                        ll kk=k+(2*j-p-q)*(a[i-1]-a[i]);
                        if(kk>lim) continue;
                        //新开一个段 
                        if(j>1) inc(f[j+1][kk][p][q],(j-1)*g[j][k][p][q]%mod);//在中间开段 
                        if(!p){//在最左边开段 
                            inc(f[j+1][kk][0][q],g[j][k][p][q]);
                            inc(f[j+1][kk][1][q],g[j][k][p][q]);
                        }
                        if(!q){//在最右边开段 
                            inc(f[j+1][kk][p][0],g[j][k][p][q]);
                            inc(f[j+1][kk][p][1],g[j][k][p][q]);
                        }
                        //延续一段 
                        if(j>1) inc(f[j][kk][p][q],2*(j-1)*g[j][k][p][q]%mod);
                        if(!p){
                            inc(f[j][kk][0][q],g[j][k][p][q]);
                            inc(f[j][kk][1][q],g[j][k][p][q]);
                        }
                        if(!q){
                            inc(f[j][kk][p][0],g[j][k][p][q]);
                            inc(f[j][kk][p][1],g[j][k][p][q]);
                        }
                        //合并两段 
                        if(j>1) inc(f[j-1][kk][p][q],(j-1)*g[j][k][p][q]%mod);
                    }
                }
            }
        }
    }
    fr(i,0,lim) ans=(ans+f[1][i][1][1])%mod;
    printf("%lld",ans);
}