bzoj4664: Count

是bzoj4498: 魔法的碰撞的哥哥题，我只写了一种

不一样的地方在于贡献有负数，第三维要保存的不能仅仅是0~L，这样空间会炸裂

考虑如何把贡献变成正的

假如要求最优解，那么一定是按顺序排，混乱度为hmax-hmin

反过来想，这启示我们hi-hj，可以用(hi - hi-1)+(hi-1 - hi-2)……(hj+1 - hj)表示出来

那么可以从小到大插入，每次插入给所有段的两端的点的贡献加上hi - hi-1

好妙啊

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

typedef long long LL;

const int _=1e2;

const int maxn=1e2+;

const int maxL=1e3+_;

const LL mod=1e9+;

int h[maxn];

LL f[][maxn][maxL][];

int main()

{

//    freopen("b.in","r",stdin);

//    freopen("b.out","w",stdout);

    int n,L;

    scanf("%d%d",&n,&L);

    if(n==){puts("");return ;}

    for(int i=;i<=n;i++)scanf("%d",&h[i]);

    sort(h+,h+n+);

    if(h[n]-h[]>L){puts("");return ;}

    int now=;

    f[now][][][]=;

    f[now][][][]=;

    for(int i=;i<n;i++)

    {

        memset(f[now^],,sizeof(f[now^]));

        for(int j=;j<=i;j++)

            for(int k=;k<=L;k++)

                for(int p=;p<=;p++)

                    if(f[now][j][k][p])

                    {

                        int d=k+(h[i+]-h[i])*(*j-p);

                        if(d<=L)

                        {

                            f[now^][j+][d][p]=(f[now^][j+][d][p]+f[now][j][k][p]*(j-p+))%mod;

                            f[now^][j][d][p]=(f[now^][j][d][p]+f[now][j][k][p]*(*j-p))%mod;

                            if(j!=)f[now^][j-][d][p]=(f[now^][j-][d][p]+f[now][j][k][p]*(j-))%mod;

                            if(p!=)

                            {

                                f[now^][j+][d][p+]=(f[now^][j+][d][p+]+f[now][j][k][p]*(-p))%mod;

                                f[now^][j][d][p+]=(f[now^][j][d][p+]+f[now][j][k][p]*(-p))%mod;

                            }

                        }

                    }

        now^=;

    }

    LL ans=;

    for(int i=;i<=L;i++)

        ans=(ans+f[now][][i][])%mod;

    printf("%lld\n",ans);

    return ;

}