题解：P9296 [POI2020] Gra platformowa / 平台游戏

· · 题解

这三种转移实在不是很优雅。给它改一下，把洞也加入状态，改成：

  1. 如果 (i,x) 不是洞，(i,x)\to(i,x+1)，代价 0。
  2. 如果 (i,x) 是洞，(i,x)\to(i+1,x)，代价 0。
  3. 如果 (i,x) 是洞，(i+1,x)\to(i,x)，代价 0。
  4. 如果 (i,x) 是洞，(i,x)\to(i,x+1)，代价 1。

记 f_{i,x} 表示从 (i,x) 出发的答案。如果有一列没有任何洞，那么这一列的 f 值都与下一列相同。于是离散化。

因为一个格子没有洞的话只有一种转移，所以不用动它。最后转移的数量和洞的数量就线性相关了，倒着计算即可。

设洞数量 K=\sum_ik_i，时间复杂度 O(n+z+K\log K)。

#include<algorithm>
#include<iostream>
int dp[100001];
long long e[2000001];
int main()
{
    std::cin.tie(0)->sync_with_stdio(0);
    int n,x,z,le=0;
    std::cin>>n>>x>>z;
    for(int i=1;i<=n;i++)
    {
        int k;
        std::cin>>k;
        while(k--)
        {
            int j;
            std::cin>>j,e[le++]=(1ll*j)<<18|i;
        }
    }
    std::sort(e,e+le,std::greater<>());
    for(int i=0;i<le;i++)
    {
        const int j=e[i]&(1<<18)-1;
        dp[j]++,j<n?dp[j]=dp[j+1]=std::min(dp[j],dp[j+1]):0;
    }
    while(z--)
    {
        int p;
        std::cin>>p,std::cout<<dp[p]<<'\n';
    }
    return 0;
}

Bonus：该题可以使用 01BFS 做到完全线性。