摩天大楼

将\(N\)个互不相同的整数\(A_1, A_2, ? , A_N\)任意排列成\(B_1, B_2, ? , B_N\)，要求\(\sum_{i=1}^{N?1}|B_{i+1} ? B_i| ≤ L\)。

计数方案数。

\(N ≤ 100, L ≤ 1000\)

题解

仓鼠《动态规划选讲》。

考虑一个把所有元素按照从大到小的顺序放到排列中正确的位置的过程。那么每次插入一个元素，其所在的连续段就是以其为根在笛卡尔树上的子树。

把原序列排序后做个差分，那么在这个过程中，每个时刻序列都形成了若干个连续段。一个连续段的端点和其相邻的还未被填上的数的差值会被拉大，拉大的数值就是当前差分的值。

所以可以记录形成的连续段的情况。设\(F[i][s][x][a ∈ \{0,1\}][b ∈\{0,1\}]\)表示考虑到第\(i\)个元素，当前差值的和为\(s\)，连续段的个数为\(x\)，序列的左右端点有没有被加入。可以根据这些信息算出，被拉大差值的两个相邻元素的数目。每次加入元素分情况讨论：新建段、紧贴着一个段、合并了两个段。

可以把这个过程看做笛卡尔树上的子树合并。然而这个转化并没有什么用……

时间复杂度\(O(N^2L)\)。

https://www.cnblogs.com/coldchair/p/12207336.html

CO int N=101,M=1001;
int A[N],F[N][N][M][3];

int main(){
	int n=read<int>(),m=read<int>();
	for(int i=1;i<=n;++i) read(A[i]);
	if(n==1) {puts("1"); return 0;}
	sort(A+1,A+n+1);
	F[0][0][0][0]=1;
	for(int i=1;i<=n;++i){
		int det=A[i]-A[i-1];
		for(int j=0;j<=i;++j)for(int k=0;k<=m;++k)
			for(int u=0;u<=2;++u)if(F[i-1][j][k][u]){
				int nk=k+det*(2*j-u);
				if(nk>m) continue;
				int f=F[i-1][j][k][u];
				chkadd(F[i][j+1][nk][u],mul(f,j-u+1)); // new
				if(u<2) // new in the border
					chkadd(F[i][j+1][nk][u+1],mul(f,1+!u));
				chkadd(F[i][j][nk][u],mul(f,2*j-u)); // stick
				if((j>u or i==n) and u<2) // stick in the border 
					chkadd(F[i][j][nk][u+1],mul(f,1+!u));
				if(j>1 and !(j==2 and u==2 and i<n)) // merge
					chkadd(F[i][j-1][nk][u],mul(f,j-1));
			}
	}
	int ans=0;
	for(int k=0;k<=m;++k)
		chkadd(ans,F[n][1][k][2]);
	printf("%d\n",ans);
	return 0;
}

摆花

小明的花店新开张，为了吸引顾客，他想在花店外摆上一圈花。小明有\(n\)盆花，从\(1\)到\(n\)编号。花店外恰有\(n\)个位置可供摆花，这些位置也从\(1\)到\(n\)编号。规定位置\(i\)的顺时针下一个位置为\(i+1\)（\(1\leq i\leq n-1\)），特别的，位置\(n\)的顺时针下一个位置为位置\(1\)。

通过调查顾客的喜好，小明给每盆花\(i\)设定了四个参数：\(a_i,b_i,c_i,d_i\)，对于一种摆花方案，小明按如下方法计算该方案的美观度：

1. 设编号为\(i\)的花所在位置的顺时针下一个位置摆的是编号为\(j\)的花，且\(i< j\)，则花\(i\)的美观度为\(a_i+b_j\)；

2. 设编号为\(i\)的花所在位置的顺时针下一个位置摆的是编号为\(j\)的花，且\(i>j\)，则花\(i\)的美观度为\(c_i+d_j\)；

3. 该方案的美观度等于所有花的美观度之和。

小明要在每个位置上摆一盆花，请计算所有摆花方案中，最大的美观度是多少。

\(n\leq 2000\)。

题解

按照编号从小到大摆花，维护连续段即可。因为这是一个环，并且这还是个最优化问题，所以代码相当的简单。

时间复杂度\(O(n^2)\)。

CO int N=2e3+10;
int a[N],b[N],c[N],d[N];
int F[N][N];

int main(){
	int n=read<int>();
	for(int i=1;i<=n;++i) read(a[i]),read(b[i]),read(c[i]),read(d[i]);
	for(int i=1;i<=n;++i)for(int j=0;j<=i-1;++j){
		F[i][j+1]=max(F[i][j+1],F[i-1][j]+d[i]+a[i]);
		if(j) F[i][j]=max(F[i][j],F[i-1][j]+max(b[i]+a[i],d[i]+c[i]));
		if(j>=2 or (i==n and j==1)) F[i][j-1]=max(F[i][j-1],F[i-1][j]+b[i]+c[i]);
	}
	printf("%d\n",F[n][0]);
	return 0;
}

LOJ2743 摩天大楼 和 test20200425 摆花

原文：https://www.cnblogs.com/autoint/p/12698693.html