题解：P10432 [JOISC 2024 Day1] 滑雪 2

# Solution

性质：如果最终 $u$ 是 $v$ 的父亲，那么 $h_u \le h_v$。

证明：

若 $c_u \ge c_v$，考虑进行下图变换，肯定不劣。

![](https://s21.ax1x.com/2024/06/05/pkYp2Pe.png)

（点权相应修改）

若 $c_u < c_v$，考虑进行下图变换，肯定不劣。

![](https://s21.ax1x.com/2024/06/05/pkYpR8H.png)

对于本题，考虑按照原有深度逐层加点。

假设当前我们考虑了所有高度 $\le i$ 的节点，目前的叶子节点有 $j$ 个接口，我们将 $k$ 个高度 $\le i$ 的节点暂时高度调整为 $i+1$ 且还没有接入树的最小代价为 $dp_{i,j,k}$。

这时我们加入了 $cnt$ 个高度为 $i+1$ 的点。基本的贪心告诉我们，现在尽量把接口给占满，剩余的调整为 $i+2$。

因此我们可以加入 $cnt+k - \max\{0,cnt+k-j\}$ 个点。转移为：

$$
dp_{i,j,k} + K \times \max\{0,cnt+k-j\} \to dp_{i+1,j,\max\{0,cnt+k-j\}}
$$

如果我们现在想要扩充接口数量怎么办？重要的观察是，对于那 $k$ 个被推迟的点，不应该在此处扩容——如果他们要扩容，早就应该交给和他们原始高度相同的点来完成了。因此，我们要用 $\min_{1 \le t \le n,h_t = i+1} \{c_t\}$ 的代价来增加接口数。这就是一个简单的完全背包问题。

我们显然要对第一维进行离散化。而观察到真正有价值的每一层，至少会把一个节点加入树，因此将 $h$ 排序，执行 $k_i = \max\{k_{i-1},h_i\}$，把所有 $k$ 进行离散化即可。

代码比较简短：

```cpp
#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=300+10;
int n,K,pre,lst=-1,h[MAXN],c[MAXN],tot,lsh[MAXN],cnt[MAXN],dp[MAXN][MAXN][MAXN],mn[MAXN];
map<int,int> mp;
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>K,memset(mn,0x3f,sizeof(mn)),memset(dp,0x3f,sizeof(dp));
	ffor(i,1,n) cin>>h[i]>>c[i],mp[h[i]]++;
	for(auto pr:mp) {
		if(lst!=-1) {
			int dt=min(pr.first-lst,pre);
			ffor(j,lst,lst+dt-1) lsh[++tot]=j;
			pre-=dt;
		}
		pre+=pr.second,lst=pr.first;
	}
	ffor(j,1,pre) lsh[++tot]=lst+j-1;
	ffor(i,1,n) cnt[i]=mp[lsh[i]];
	ffor(i,1,n) {
		int id=lower_bound(lsh+1,lsh+n+1,h[i])-lsh;
		mn[id]=min(mn[id],c[i]);
	}
	dp[0][1][0]=0;
	ffor(i,0,n-1) {
		ffor(j,0,n) ffor(k,0,n) if(dp[i][j][k]!=0x3f3f3f3f3f3f3f3f) {
			int l=max(0ll,cnt[i+1]+k-j);
			dp[i+1][j][l]=min(dp[i+1][j][l],dp[i][j][k]+K*l); 
		}
		ffor(j,1,n) ffor(k,0,n) dp[i+1][j][k]=min(dp[i+1][j][k],dp[i+1][j-1][k]+mn[i+1]);
	}
	int ans=LONG_LONG_MAX;
	ffor(i,0,n) ans=min(ans,dp[n][i][0]);
	cout<<ans;
	return 0;
}
```

正在渲染内容...