简介

有一类问题，他们需要计算满足在序列上插入给定顺序的元素，其贡献/限制只与两旁的元素有关，但元素插入的位置是不一定的，所以会有代价的最值和方案数的统计。而对于这类问题，我们其实可以不关心每一次插入的具体位置在哪里，而只关注他的相对位置（比如在某个数左边、在某个数左边且与其相邻之类的），从而将状态大大简化。

模型

通常以二维表示 dp[i][j] 表示插入到第 i 个元素，前 i-1 个元素已经插入到序列上，一共形成了 j 个连通块的方案数/代价。转移有三种大类，分别是合并两个连通块、新加一个连通块、延续一个连通块。

考虑为什么要用连通块表示相对位置的信息。因为连通块可以表示左右是否有数、以及左右的数是否与其相邻。这里面有个隐藏的参数是当前场上的元素数量，但我们发现用 i 就表示完了。

纸上觉来终觉浅，下面进入实战。

题目讲解

1.摩天大楼

首先注意到限制有绝对值，考虑将 a[i] 按照从大到小的顺序插入到序列中，那么绝对值的限制就去掉了。我们发现此时插入的元素顺序确定，并且发现当前插入一个数的代价与其它已经在序列上的数有关，符合模型，即可使用连通块dp 解决。细节交给读者思考。

#include<bits/stdc++.h>
using namespace std;
#define ll long long

const ll Mod=1e9+7;

int n,L;
int a[105];
ll dp[105][105][1005][2][2];
//int now[105][105][1005][2][2];

bool cmp(int x,int y){ return x>y; }

int main(){
	cin>>n>>L;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	dp[1][1][0][0][0]=dp[1][1][0][1][1]=dp[1][1][0][0][1]=dp[1][1][0][1][0]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++) for(int k=0;k<=L;k++) for(int p=0;p<=1;p++) for(int q=0;q<=1;q++) if(dp[i-1][j][k][p][q]){
			int now=(a[i-1]-a[i])*(j*2-p-q);
			if(k+now>L) continue;
			if(j>1) dp[i][j-1][k+now][p][q]+=dp[i-1][j][k][p][q]*(j-1),dp[i][j-1][k+now][p][q]%=Mod;
			if(j>1) dp[i][j+1][k+now][p][q]+=dp[i-1][j][k][p][q]*(j-1),dp[i][j+1][k+now][p][q]%=Mod;
			if(j>1) dp[i][j][k+now][p][q]+=dp[i-1][j][k][p][q]*(2*j-2),dp[i][j][k+now][p][q]%=Mod; 
			if(!p){
				dp[i][j][k+now][1][q]+=dp[i-1][j][k][p][q],dp[i][j][k+now][1][q]%=Mod; 
				dp[i][j][k+now][0][q]+=dp[i-1][j][k][p][q],dp[i][j][k+now][0][q]%=Mod;
				dp[i][j+1][k+now][1][q]+=dp[i-1][j][k][p][q],dp[i][j+1][k+now][1][q]%=Mod; 
				dp[i][j+1][k+now][0][q]+=dp[i-1][j][k][p][q],dp[i][j+1][k+now][0][q]%=Mod;
			}
			if(!q){
				dp[i][j][k+now][p][1]+=dp[i-1][j][k][p][q],dp[i][j][k+now][p][1]%=Mod; 
				dp[i][j][k+now][p][0]+=dp[i-1][j][k][p][q],dp[i][j][k+now][p][0]%=Mod;
				dp[i][j+1][k+now][p][1]+=dp[i-1][j][k][p][q],dp[i][j+1][k+now][p][1]%=Mod;
				dp[i][j+1][k+now][p][0]+=dp[i-1][j][k][p][q],dp[i][j+1][k+now][p][0]%=Mod;
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=L;i++) ans+=dp[n][1][i][1][1],ans%=Mod;
	cout<<ans<<endl;
	return 0;
}

2.P5999

题解看了好久没看懂，u群问了一个多小时，这下听懂了。对于这类问题我们转换一下，改为往操作序列上面依次放第 i 个草丛。注意到第 s 个草丛和第 t 个草丛在操作序列上的相对位置也需要特判。

你们他妈注意了，第一步转换很重要！！！非常重要！！！！这才是能在 `i==s||i==t` 特判的原因！！！！

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll Mod=1e9+7;

ll dp[2005][2005];
int n,s,t;

int main(){
	cin>>n>>s>>t;
	dp[1][1]=1;
	for(int i=2;i<=n;i++) for(int j=1;j<=i;j++){
		if(i==s||i==t) dp[i][j]=dp[i-1][j-1]+dp[i-1][j],dp[i][j]%=Mod;
		else dp[i][j]=dp[i-1][j-1]*(j-(i>s)-(i>t))%Mod+dp[i-1][j+1]*j%Mod;	
	}
	cout<<dp[n][1]<<endl;
	return 0;
}