自动搬运

查看原文

来自洛谷，原作者为

	是青白呀 咕咕咕？咕咕咕！

搬运于2025-08-24 22:57:55，当前版本为作者最后更新于2024-07-19 20:58:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

喵喵喵，性质题。

首先是一个最基本的观察：

性质 $1$：对于同一个点，不可能既抬高海拔，又加装新的连接设施。

考虑反证：不妨设 $x$ 点抬高海拔后连边向 $y$，连向 $x$ 的其中两个点为 $a$ 和 $b$，且 $a$ 海拔较低。显然在抬高海拔前，$H_x<H_y$。若 $C_x<C_y$，则可以放弃抬高海拔的操作，直接将 $y$ 改连向 $x$，将 $a,b$ 中的任意一个改连向 $y$；否则可以将 $a,b$ 中的任意一个改连向 $y$，两种情况的修改下，花费均更小。

性质 $2$：存在一种最优策略，使得每一个高度上都至少有 $1$ 个点不被抬高，且这个点一定是该高度上 $C$ 最小的点。

首先，我们显然不可能抬高所有点，让该高度空置。其次，若有若干个点被抬高到当前高度，则不难发现，保留原来就在这个高度的点一定更优，因为他们都会为更高的位置提供 $1$ 个免费设施，保留原来就在这个高度的点可能能提供 $C$ 更小的新增设施的选择。因此我们可以在每个高度上保留 $C$ 最小的点。

此时可以开始考虑 dp。我们按高度从低到高扫描，设 $dp_{i,j,k}$ 表示考虑到高度 $i$，前面的有效接口数量为 $j$，之前的所有高度中，有 $k$ 个点被拔高到了该位置，且还要继续拔高的最小花费。下面考虑 $i$ 向 $i+1$ 的转移。

• 不妨首先将高度 $i+1$ 处的 $cnt_{i+1}$ 个点和 $j$ 合并，得到的新状态是 $dp_{i+1,j,k+cnt_{i+1}}$，代价是 $k\times K$。

• 枚举连到现有接口的点数 $x\leq j$，得到的新状态是 $dp_{i+1,j,k+cnt_{i+1}-x}$，代价不变。

• 枚举在前面新增接口的点数 $y\leq k+cnt_{i+1}-x$，得到的新状态是 $dp_{i+1,j+y,k+cnt_{i+1}-x-y}$。设 $minc_i$ 表示高度 $i$ 及之前的所有点中最小的 $C$，根据性质 $1$ 和性质 $2$，不难得出此步的代价为 $y\times minc_i$。

综上，我们对每个状态枚举 $x,y$，可得到转移 $dp_{i+1,j+y,k+cnt_{i+1}-x-y}\gets dp_{i,j,k}+y\times minc_i+k\times K$。复杂度 $O(n^4H)$，需要继续找性质优化。

性质 $3$：每一个高度都一定会尽可能用完上一个高度留下来的所有 $j$ 个免费设施。

原因很显然：使用一个免费设施后，自己也会产生一个新的免费设施位置，不会使得免费位置减少，所以能用就用。因此 $x$ 的枚举可以去除，直接根据 $j$ 和 $k+cnt_{i+1}$ 的大小分类转移即可。

还可以发现的是，$y$ 带来的代价是一个类似完全背包的东西，因而我们从小往大枚举 $j$，从大往小枚举 $k$，在 $j<k+cnt_{i+1}$ 的情况下（此时 $x=j$）新增内部转移 $dp_{i+1,j+1,k+cnt_{i+1}-j-1}\gets dp_{i+1,j,k+cnt_{i+1}-j}+minc_i$ 即可去除 $y$ 的枚举。此时复杂度来到 $O(n^2H)$。

最后一步显然是离散化高度。考虑哪些高度是有效的。

性质 $4$：有效的高度是不增加任何额外设施，仅将所有点在高度上往后排开，每个高度安排一个点，得到的所有有点的高度。

这些高度显然是必要的，它们对应只增加海拔而不新建设施的方案。充分的原因是，根据性质 $2$ 和性质 $3$，若新建了一个额外设施，则每个点的实际高度会往回缩，填满新建额外设施带来的新的可行位置；而这些点显然不能缩得比原始高度更低。不难发现，该性质中提到的有效高度，覆盖了往回缩的过程中会遇到的所有高度，因此这些高度是足够的。

此时，我们可以将所有有效高度离散化至 $O(n)$ 级别，总复杂度即可做到 $O(n^3)$。

需要注意的是，转移中 $k\times \Delta H\times K$ 可能达到 $10^{21}$ 级别，但不难通过抬高除酒店位置外所有最低点的海拔 $1$，并将所有点直接连向酒店的方式得到一个代价不超过 $10^{12}$ 的解，因而在 dp 过程中将所有出现的值对 $10^{12}$ 取 $\min$ 即可避免超过 long long 的范围。

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long 
#define qingbai 666
using namespace std;
typedef long long ll;
const int N=305,M=105,inf=(ll)1e18+7,mo=998244353;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int upp=(ll)1e12;
int n,co,h[N],lsh[N],cntl,c[N];
int dp[N][N][N],minc[N],cntp[N],sumc[N];
signed main(){
	read(n),read(co);
	rep(i,1,n)
	    read(h[i]),read(c[i]),lsh[++cntl]=h[i];
	sort(lsh+1,lsh+cntl+1);
	rep(i,2,cntl)
	    lsh[i]=max(lsh[i],lsh[i-1]+1);//离散化，将点铺开
	rep(i,1,n)
	    h[i]=lower_bound(lsh+1,lsh+cntl+1,h[i])-lsh;
	rep(i,1,cntl)
	    minc[i]=inf;
	rep(i,1,n)
	    cntp[h[i]]++,minc[h[i]]=min(minc[h[i]],c[i]);
	minc[0]=inf;   
	rep(i,1,cntl)
	    minc[i]=min(minc[i],minc[i-1]),sumc[i]=sumc[i-1]+cntp[i];
	rep(i,0,cntl){
		rep(j,0,n+2){
			rep(k,0,n+2)
			    dp[i][j][k]=upp;
		}
	}
	dp[1][1][cntp[1]-1]=0;
	rep(i,1,cntl-1){
		rep(j,0,n){
			repp(k,max(0ll,sumc[i]-1),0){
				int nk=k+cntp[i+1],niv;
				if(k&&(lsh[i+1]-lsh[i])*co>upp)niv=upp+1;
				else niv=k*(lsh[i+1]-lsh[i])*co;
				if(!i)nk--;
				if(nk<=j)dp[i+1][j][0]=min(dp[i+1][j][0],dp[i][j][k]+niv);
				else{
					dp[i+1][j][nk-j]=min(dp[i+1][j][nk-j],dp[i][j][k]+niv);
					dp[i+1][j+1][nk-j-1]=min(dp[i+1][j+1][nk-j-1],dp[i+1][j][nk-j]+minc[i]);
				}
			} 
		}
	}
	int ans=inf;
	rep(j,0,n)
	    ans=min(ans,dp[cntl][j][0]);
	printf("%lld\n",ans);
	return 0;
}