JZOJ 6439. 【GDOI2020模拟01.17】小 ω 数排列_综合

JZOJ 6439. 【GDOI2020模拟01.17】小 ω 数排列

题目

Description

在这里插入图片描述

Input

在这里插入图片描述

Output

在这里插入图片描述

Sample Input

Sample Input1
4 10
3 6 2 9

Sample Input2
8 35
3 7 1 5 10 2 11 6

Sample Output

Sample Output1
6
【样例 1 解释】
共有 6 个排列符合条件，它们是 (1, 3, 2, 4),(2, 4, 1, 3),(3, 1, 2, 4),(3, 1, 4, 2),(4, 2, 1, 3),(4, 2, 3, 1)。

Sample Output2
31384

Data Constraint

在这里插入图片描述

题解

第一眼就是DP，先考虑暴力做法，
设 $f[i][j][k]$ 表示选出的数状压后为 $i$ ，当前最后一个数为 $j$ ，绝对值之和为 $k$ 的方案数，转移显然。
正解也是DP，方法比较巧妙。
因为式子中的绝对值不是很好处理，所以想办法去掉它，最直接的办法就是先排序后再按从小到大的顺序依次加入，
但这样并不知道要将当前数加入到什么位置，那怎么样才能保证能不重不漏地得出各种符合条件的排列呢？
可以这样想，加入时不一定和前面已经加入的连在一起，而是后面才不断加入使前面的分散的段合并起来。
设 $f[i][j][k]$ 表示加入了 $i$ 个数，目前有 $j$ 个分散的段，答案为 $k$ 的方案数，
至于答案 $k$ 如何更新，其实与 $a[i]$ 加入在哪个数旁边并没有关系，区别在于它是否自成一段，是否在边界，是否连接两段，
因为边界情况特殊，又要保证只有两个边界，所以再设多一维 $l$ 表示当前已经确定的边界的个数，
转移情况有五种：
1、加入 $a[i]$ 自成一段且不在边界；
2、加入 $a[i]$ 在某一段的一端且不在边界；
3、加入 $a[i]$ 连接在不相连的两段中间；
4、加入 $a[i]$ 自成一段放在边界；
5、加入 $a[i]$ 在某一段的一端且成为边界。
考虑每种转移对 $k$ 的贡献（注意符号有正有负）：
1、 $a[i]$ 会被后来加在它左右两边的给减去，所以贡献是 $-2*a[i]$ ；
2、 $a[i]$ 需要加上一个用来减去它旁边的，也会被后来加在旁边的给减去，所以贡献是 $0$ ；
3、 $a[i]$ 需要加上两个用来减去它左右两边的，所以贡献是 $2*a[i]$ ；
4、 $a[i]$ 会被后来加在它一边的给减去，所以贡献是 $-a[i]$ ；
5、 $a[i]$ 需要加上一个用来减去它旁边的，且另一边没有数了，所以贡献是 $a[i]$ ，
其他对于 $i,j,l$ 的变化显然。
但这样一来 $k$ 值的变化范围特别大，还是不能过，所以想办法控制 $k$ 的范围。
首先把每个 $a[i]$ 减去 $a[i]_{max}$ ，但这还不够，
发现每一次填入 $a[i]$ 时，对所有 $k$ 的贡献都可以看作是 $(a[i]-a[i-1])*(2*j-l)$ ，
那么这样就全是正的了，如果大于 $L$ 即可退出，
于是 $k$ 的范围被控制在了 $[0,L]$ ，可以愉快地通过此题。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1001
#define md 1000000007
#define ll long long
int a[N],t[N];
int f[2][110][N][3];
int main()
{int n,L,i,j,k,l;scanf("%d%d",&n,&L);if(n==1) {printf("1");return 0;}for(i=1;i<=n;i++) scanf("%d",&a[i]);if(n==2){if(a[1]-a[2]<=L&&a[2]-a[1]<=L) printf("2"); else printf("0");return 0;}sort(a+1,a+n+1);if(a[n]-a[1]>L){printf("0");return 0;}for(i=n;i;i--) a[i]-=a[1];for(i=1;i<=n;i++) t[i]=a[i]-a[i-1];f[0][0][0][0]=1;for(i=0;i<n;i++){memset(f[1-i%2],0,sizeof(f[1-i%2]));for(j=0;j<=n;j++) {for(k=0;k+t[i+1]*(2*j-2)<=L&&k<=L;k++){for(l=0;l<3;l++) if(f[i%2][j][k][l]){int x=a[i+1],k1=k+t[i+1]*(2*j-l);if(k1>L) continue;if(j<n) f[1-i%2][j+1][k1][l]=(f[1-i%2][j+1][k1][l]+f[i%2][j][k][l])%md;ll s=2*j-l;f[1-i%2][j][k1][l]=(f[1-i%2][j][k1][l]+f[i%2][j][k][l]*s)%md;s=(j-l)*(j-1);if(i+1==n) s++;if(2*j-l>=2&&j>=2) f[1-i%2][j-1][k1][l]=(f[1-i%2][j-1][k1][l]+f[i%2][j][k][l]*s)%md;s=2-l;if(j<n&&l<2) f[1-i%2][j+1][k1][l+1]=(f[1-i%2][j+1][k1][l+1]+f[i%2][j][k][l]*s)%md;s=j*2-j*l-l;if(i+1==n) s++;if(l<2&&j) f[1-i%2][j][k1][l+1]=(f[1-i%2][j][k1][l+1]+f[i%2][j][k][l]*s)%md;}}}}int ans=0;for(k=0;k<=L;k++) ans=(ans+f[n%2][1][k][2])%md;printf("%d",ans);return 0;
}