自动搬运

查看原文

来自洛谷，原作者为

	JohnJoeZhu 我要认真学习whk！！！

搬运于2025-08-24 21:50:31，当前版本为作者最后更新于2020-08-05 09:29:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题面传送门

1.寻找算法方向

1.1 数据范围

首先我们发现，n竟然只有50！

说明我们肯定是要多次枚举位置的

时间复杂度估计在$O(n^2m)$至$O(n^3m)$之间

1.2 初步暴力

暴力的目的是求出在解题过程中我们大致需要枚举的量

首先我们可以枚举每个点的取值，然后统计有效区间

实际大致可以做到$O(n\space max(c))$

1.3 明确算法

暴力不好写，而从暴力得到的复杂度低于上限，那是否说明我们可以通过$O(n)$至$O(n^2)$的枚举来快速得到答案

可是我们发现每个人的要求是区间性的，那么我们是不是可以对每个区间单独考虑，然后再合并

这个思想，不就是区间dp吗？（当然你也可以感性理解，大胆猜想qwq）

2.完善dp步骤

既然是dp了，那就肯定要走dp那几步的

2.1 设计状态

常规设计是$f[i][j]$表示区间$[i,j]$的收益最大值

由于我们暴力发现需要枚举最小值的位置（即断点）和最小值，所以我们应该这样子设计

$f[i][j][k]$表示区间$[i,j]$，最小值为$k$的最大收益

2.2 确定转移方程

由于我们要枚举最小值的位置（即断点），那就可以这样子写

$f[i][j][k]=max(f[i][l-1][k]+f[l+1][j][k]+val(i,j,l,k))(i<=l<=j)$

$val(i,j,l,k)$表示在区间$[i,j]$内的顾客，当最小值在$l$处，最小值为$k$的价值

$val(i,j,l,k)=cnt(i,j,l,k)*k$

$cnt(i,j,l,k)$也就是在区间$[i,j]$内的顾客，当最小值在$l$处，最小值为$k$时，在$l$处消费的顾客数量

如果我们稍加思考，我们应该发现我们取值后的结果是可传递的

也就是说，$f[i][j][k]=max(f[i][j][k],f[i][j][k+1])$

因为我们选择k为最小值，k+1也是可以选的，顾客少了可是每个人交的钱多了

所以应该有两个方程

$$f[i][j][k]=max\left\{ \begin{aligned} f[i][j][k+1]\\ max(f[i][l-1][k]+f[l+1][j][k]+val(i,j,l,k))(i<=l<=j)\\ \end{aligned} \right. $$

2.3 得到答案

显然，答案应该是$f[1][n][k]$

那么k应该是多少呢？

我们现在知道，k=1时已经把其他的k的答案都传递了，所以k就是1啦

那么方案呢？（注意有SPJ）

常规操作，我们在枚举过程中记录下断点即最优决策点，再记录下最优取值k

这里要注意后者是指向第二个方程的，也就是说，最小值为k，它的最优取值不一定为k

然后就递归求解，直接输出

2.4 优化算法

咦？解决什么问题呢？

我们分析一下时间复杂度

枚举区间状态$O(n^2\space max(c_i))$

枚举断点$O(n)$

转移方程（即求val/cnt）$O(m)$

那复杂度就是$O(n^3m\space max(c_i))$

显然我们可以优化

首先，我们发现求val应该是可以优化的

因为对于一个区间，在某一位置取某一固定值，顾客数是不变的

那么就是说，我们可以预处理cnt，复杂度$O(m\space max(c_i))$

然后我们就看到了一直没有处理的$O(max(c_i))$

这是一个题目没有给出的值（似乎是$5e5$由于某些原因不见了）

显然我们是不可以使用它的

但是我们真的需要从$1-max(c_i)$枚举吗？

如果我们可以取$c_i$和$c_j(c_i>c_j)$，只有在两个临界点才会产生贡献

也就是说，当我们取$(c_j,c_i)$中的值时，既不能够增加顾客数量，又不能够增大收入（本来的$c_i$的收入越来越小了）

所以我们得到每一个店的标价，只有在某一个$c_i$取值才会最优

那就离散化！

我们再来计算时间复杂度

枚举区间状态$O(n^2m)$

枚举断点$O(n)$

求cnt（这里应该好理解），此时不需要嵌套 $O(nm)$

这里外层有一个$O(n^2)$的枚举区间

所以总复杂度应该是$O(n^3m)$

3. 代码实现

相信来到紫题的大佬都很牛逼，所以这里只给出部分代码

3.1 离散化

这就太容易了吧

3.2 对于每个区间求出cnt

for(int len=1;len<=n;len++)
		for(int i=1,j=i+len-1;j<=n;i++,j=i+len-1)//枚举区间
		{
			for(int k=i;k<=j;k++)
				for(int l=1;l<=tot;l++)//tot为离散化后实际有多少个不同的c
					g[k][l]=0;//因为重复，所以要清零，这里是cnt
			for(int k=1;k<=m;k++)
				if(a[k]>=i&&j>=b[k])//注意顾客区间必须在枚举的区间内，否则顾客可能在其他区间内消费
					for(int l=a[k];l<=b[k];l++)
						g[l][c[k]]++;
			for(int k=i;k<=j;k++)
				for(int l=tot-1;l;l--)//如果l可以，那么比l小的都可以
					g[k][l]+=g[k][l+1];//求出每个点，每个价值可以收获的顾客
      		}

3.3 转移方程

for(int len=1;len<=n;len++)
		for(int i=1,j=i+len-1;j<=n;i++,j=i+len-1)
			for(int k=tot;k;k--)//枚举最小值
			{
				int anss=0,sum;
				for(int l=i;l<=j;l++)//枚举断点
					if((sum=f[i][l-1][k]+f[l+1][j][k]+g[l][k]*d[k])>=anss) anss=sum,num[i][j][k]=l;//转移方程显然,num存决策点
				if(anss>=f[i][j][k+1]) f[i][j][k]=anss,val[i][j][k]=k;//与k+1比较（由于不同情况需要更新的内容不同 ，val为最优值
				else f[i][j][k]=f[i][j][k+1],val[i][j][k]=val[i][j][k+1];
			 } 

3.4 求出答案

void gans(int l,int r,int k)
{
	if(l>r) return;
	int point=num[l][r][k=val[l][r][k]];//得到决策点，注意这里的k不一定是原来的k，应该是最优的k
	ans[point]=d[k];//答案函数
	gans(l,point-1,k),gans(point+1,r,k);//递归求解
}

然后完整代码就不给出了

然后就没有然后了

完结撒花

顺手广告