题解：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。

考虑转移：

转移有两种方式：

  1. 通过 ”提升海拔“ 转移。设高度为 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 不变；
  2. 通过 ”建立接口“ 转移。易得 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)。

代码：

#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;
};