题解：P10432 [JOIST 2024] 滑雪 2 / Ski 2

神秘性质题，挺不错的。

性质 $1$

对于同一个点，我们不能同时对其提升海拔与建立接口

考虑设

x

提升海拔后连向

y

，则必有

h_x < h_y

。

若

c_x < c_y

，则可以放弃提升

x

的海拔，转而将

y

连向

x

，代价一定更小，这种情况下我们只有可能建立接口，一定不会提升海拔；

若

c_x \geq c_y

，则可以考虑把所有连向

x

的非免费接口的点都连向

y

的接口，这种情况下我们只有可能提升海拔，一定不会建立接口。

性质 $2$

存在一种最优策略，使得每一个高度 $i$ 上都至少有一个点不被提高，且该点为原本海拔为 $i$ 的所有点中 $c$ 值最小的

首先我们显然不能把该高度的所有节点都向上提。

其次，我们如果要在当前高度进行选点，一定是选择当前高度下

c

值尽量小的点。

最后，如果我们选的点不是原本就在该高度下的点，那么显然有这个点的

c

值小于原本在该高度下的所有点的

c

值，于是由刚刚的推导，我们完全没有必要将这个点向上提。

综上，性质得证。

性质 $3$

每一个高度都会尽量用完从上一个高度提升海拔过来的所有点

考虑这部分点已经被提升过海拔，于是由性质

1

，我们不可能再对它们建立接口。于是这部分点唯一的价值就是提供一个免费接口。于是为了让这部分接口被更多的节点使用到，同时也为了让提升海拔的代价尽量小，我们肯定要让它们尽量只提升一次海拔。

于是可以设计状态

dp_{i,j,k}

表示在只考虑高度不超过

i

的所有节点时，当前共有

j

个可用的接口，假设我们已经将

k

个高度为

i

的节点移到了高度

i + 1

，需要消耗的最小代价。注意这

j

个接口是不包括我们移动的那

k

个节点的接口的，因为这

k

个接口实际上是不可用的。

下将高度

i

称为第

i

层。

考虑初始化：显然有

dp_{minh,1,0}=0

，其中

minh

为海拔最低的点的高度。

dp

数组的其余部分置为

\inf

。

考虑转移：

转移有两种方式：

通过 ”提升海拔“ 转移。设高度为 $i+1$ 的节点共有 $x$ 个，则有 $dp_{i,j,k} + K \cdot \max(x+k-j , 0) \to dp_{i+1,j,\max(x+k-j , 0)}$ 。这个式子含义比较显然。我们考虑第 $i+1$ 层的点会有多少不能向前面连边，显然这样的点共有 $\max(x+k-j)$ 个，于是将其向上移动即可。并且我们有：对于每一个被占用的接口，它都是由一个免费接口还没有被占用的点占用的，故我们总的可用接口数量 $j$ 不变；
通过 ”建立接口“ 转移。易得 $dp_{i,j,k} + \min c_i \to dp_{i,j+1,k}$ ，其中 $\min c_i$ 为原本海拔不超过 $i$ 的点中 $c$ 值的最小值。

显然

k

这一维的状态数不超过

n

，于是考虑

j

这一维。显然如果我们可用的接口如果大于了

n

个，那一部分接口就会被浪费，不够优秀，故

j

这一维的状态数也不超过

n

。于是我们得到了一个

O(n^2H)

的算法，注意到

H

极大，考虑将

H

离散化，于是要考虑哪一部分

h

值是有用的。

如果高度

i

上有

cnt_i

个点，显然我们这一层的节点可能走到的所有高度为

i,i+1,\dots,i+cnt_i-1

，将这些高度加入离散化数组即可。当然如果在展开高度的途中遇到了另一个高度重合的点，要将这部分点放在一起继续展开。

显然在离散化后，高度最多只剩下

n

种，故最终时间复杂度为

O(n^3)

。

代码：

CPP

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair <int , int>
#define pb push_back
#define fi first
#define se second
#define fastio ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
using namespace std;
const int MAXN = 330 , INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
struct node
{
	int h;
	ll c;
};
int n;
int tmpk[MAXN] , cnt[MAXN];
ll K , cval[MAXN] , dp[MAXN][MAXN][MAXN];
node a[MAXN];
int main()
{
	fastio;
	cin >> n >> K;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i].h >> a[i].c;
		tmpk[i] = a[i].h;
	}
	sort(tmpk + 1 , tmpk + 1 + n);
	memset(cval , INF , sizeof(cval));
	memset(dp , INF , sizeof(dp));
	tmpk[0] = -INF;
	for(int i = 1 ; i <= n ; i++) tmpk[i] = max(tmpk[i] , tmpk[i - 1] + 1);
	for(int i = 1 ; i <= n ; i++)
	{
		a[i].h = lower_bound(tmpk + 1 , tmpk + 1 + n , a[i].h) - tmpk;
		cnt[a[i].h]++;
		cval[a[i].h] = min(cval[a[i].h] , a[i].c);
	}
	for(int i = 1 ; i <= n ; i++) cval[i] = min(cval[i] , cval[i - 1]);
	dp[0][1][0] = 0;
	for(int i = 0 ; i <= n ; i++)
	{
		for(int j = 1 ; j <= n ; j++)
		{
			for(int k = 0 ; k <= n ; k++)
			{
				if(dp[i][j][k] == LINF) continue;
				dp[i + 1][j][max(0 , cnt[i + 1] + k - j)] = min(dp[i + 1][j][max(0 , cnt[i + 1] + k - j)] , dp[i][j][k] + K * max(0 , cnt[i + 1] + k - j));
				dp[i][j + 1][k] = min(dp[i][j + 1][k] , dp[i][j][k] + cval[i]);
				// cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k] << endl;
			}
		}
	}
	long long ans = LINF;
	for(int i = 1 ; i <= n ; i++) ans = min(ans , dp[n][i][0]);
	cout << ans;
	return 0;
};

题解：P10432 [JOIST 2024] 滑雪 2 / Ski 2

文章操作

相关推荐

评论

题解：P10432 [JOIST 2024] 滑雪 2 / Ski 2