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

· · 题解

喵喵喵，性质题。

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

性质 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 的转移。

综上，我们对每个状态枚举 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;
}