【COCI 2020/2021 Round #2 D】Magneti (DP)

Magneti

题目链接：COCI 2020/2021 Round #2 D

题目大意

给你 n 个物品,each has a value,and different items.
然后有一个长度为 L 的板子,Then you have to put the items on top of each hour,Makes the distance between the two items not less than the maximum of their weights.
Then ask you how many ways.

思路

考虑 DP,found unlikely DP,Because it's about two,但是不可以 $2^n$.

考虑转化一下,find that if we determine the order,What is the minimum length of the board?？
Think about it, you will find that the two $\max (a_i,a_{i+1})$ 的空位,The total required position is the sum of these plus $n$.
We can use the plug-in method to allocate the extra position.

The question then becomes asking for each $\max$ 的和的结果,How many sequences are there?？
Considering the contribution location,That is the big one,So consider adding numbers from small to large,The how many adjacent in front of that every time is how many their contribution.
Then consider that there will be several blocks after putting it in,Blocks are not adjacent,Then use the numbers to combine.
Then make a DP：$f_{i,j,k,0/1/2,w}$ 为前 $i$ 个数放进去,one side empty $j$ 个块,empty on both sides $k$ 个块,Two blocks of blocks have been placed $0/1/2$ 个,当前 $\max$ 的和为 $w$.
Then classify and discuss transfer.

发现会超时,因为是 $O(n^{3}L)$ 的.
考虑优化,Looking at the transfer formula, you will find that $j$ It will only be added when it is at both ends,所以 $j$ The size is actually $0/1/2$,然后变成 $O(n^{2}L)$ 就可以过了.

代码

#include<cstdio>
#include<algorithm>
#define mo 1000000007

using namespace std;

const int N = 51;
const int M = 1e4 + 10; 
int n, L, a[N], jc[M], inv[M], invs[M];
int f[2][3][N][3][M], inv2;

int add(int x, int y) {
    return x + y >= mo ? x + y - mo : x + y;}
int dec(int x, int y) {
    return x < y ? x - y + mo : x - y;}
int mul(int x, int y) {
    return 1ll * x * y % mo;}
int C(int x, int y) {
    if (y < 0 || y > x) return 0; return mul(jc[x], mul(invs[y], invs[x - y]));}
int ksm(int x, int y) {
    int re = 1; while (y) {
    if (y & 1) re = mul(re, x); x = mul(x, x); y >>= 1;} return re;}

void Init() {
    
	jc[0] = 1; for (int i = 1; i < M; i++) jc[i] = mul(jc[i - 1], i);
	inv[0] = inv[1] = 1; for (int i = 2; i < M; i++) inv[i] = mul(inv[mo % i], mo - mo / i);
	invs[0] = 1; for (int i = 1; i < M; i++) invs[i] = mul(invs[i - 1], inv[i]);
	inv2 = ksm(2, mo - 2);
}

void ck(int &x, int y) {
    
	x = add(x, y);
}

int main() {
    
// printf("%.3lf", (sizeof(f) * 2) / 1024.0 / 1024.0);
	
	freopen("magnet.in", "r", stdin);
	freopen("magnet.out", "w", stdout);
	
	Init();
	
	scanf("%d %d", &n, &L);
// for (int i = 1; i <= n; i++) a[i] = 1;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1);
	
	if (n == 1) {
    
		printf("%d", L); return 0;
	}
	
	f[0][0][0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
    
		for (int j = 0; j < 3; j++)
			for (int k = 0; k + j < i; k++)
				for (int l = 0; l <= 2; l++)
					for (int s = 0; s <= L; s++)
						if (f[(i & 1) ^ 1][j][k][l][s]) {
    
							int x = f[(i & 1) ^ 1][j][k][l][s]; f[(i & 1) ^ 1][j][k][l][s] = 0;
							if (l < 2) {
    
								ck(f[i & 1][j + 1][k][l + 1][s], (2 - l) * x);
								if (s + a[i] <= L) {
    
									if (j) ck(f[i & 1][j - 1][k][l + 1][s + a[i]], mul(x, j));
									if (k) ck(f[i & 1][j + 1][k - 1][l + 1][s + a[i]], mul(x, k * (2 - l)));
								}
							}
							if (s + a[i] <= L) {
    
								if (j) ck(f[i & 1][j][k][l][s + a[i]], mul(x, j));
								if (k) ck(f[i & 1][j][k][l][s + a[i]], mul(x, 2 * k));
							}
							if (s + a[i] + a[i] <= L) {
    
								if (j > 1) ck(f[i & 1][j - 2][k][l][s + a[i] + a[i]], x);
								if (k > 1) ck(f[i & 1][j][k - 1][l][s + a[i] + a[i]], mul(x, mul(k, k - 1)));
								if (j && k) ck(f[i & 1][j][k - 1][l][s + a[i] + a[i]], mul(x, mul(j, k)));
							}
							ck(f[i & 1][j][k + 1][l][s], x);
						}
	}
	
	int ans = 0;
	for (int i = 0; i <= L; i++) {
    
		ck(ans, mul(f[n & 1][0][0][2][i], C(L - i + n - 1, n)));
	}
	printf("%d", ans);
	
	return 0;
}