BZOJ 4664: Count 插块DP

题解链接

CODE

#pragma GCC optimize (2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int MAXL = 1005;
const int mod = 1e9 + 7;
int dp[2][MAXN][3][MAXL];
int n, L, h[MAXN];
inline void add(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }
int main () {
	scanf("%d%d", &n, &L);
	if(n == 1) { puts("1"); return 0; }
	for(int i = 1; i <= n; ++i) scanf("%d", &h[i]);
	sort(h + 1, h + n + 1);
	int cur = 0;
	dp[cur][1][2][0] = 1;
	dp[cur][1][1][0] = 2;
	for(int i = 2; i <= n; ++i) {
		cur ^= 1;
		memset(dp[cur], 0, sizeof dp[cur]);
		for(int j = 1; j <= i; ++j)
			for(int k = 0; k < 3; ++k) {
				int w = (h[i] - h[i-1]) * (2*(j-1) + k), nxt;
				for(int l = 0; l <= L; ++l) {
					if((nxt = (l + w)) > L) break;
					if(!dp[cur^1][j][k][l]) continue;
					if(k) {
						add(dp[cur][j+1][k-1][nxt], 1ll * dp[cur^1][j][k][l] * k % mod); // 新建边界
						add(dp[cur][j][k-1][nxt], 1ll * dp[cur^1][j][k][l] * k % mod); // 把一段变成边界
					}
					add(dp[cur][j+1][k][nxt], 1ll * dp[cur^1][j][k][l] * ((j-1) + k) % mod); //新建一段
					add(dp[cur][j][k][nxt], 1ll * dp[cur^1][j][k][l] * (2*(j-1) + k) % mod);	//加在一边
					add(dp[cur][j-1][k][nxt], 1ll * dp[cur^1][j][k][l] * (j-1) % mod); //链接两段
				}
			}
	}
	int ans = 0;
	for(int i = 0; i <= L; ++i) add(ans, dp[cur][1][0][i]);
	printf("%d
", ans);
}