题解：P15361 「WYZOI R2」拜年

· · 题解

原题：P15361

算法分析

考虑枚举 l。

需要在枚举 l 时确定 r 的下限。\ 设定一个函数 F(x)：

若不存在从 (1,1) 到 (2,n) 的路径，能使得路径上的每个点 (i,j) 都满足 a_{i,j}\ge x，则 F(x)=+\infty（代码中用 -1 表示）。\ 考虑所有满足上述条件的路径，对于每条路径 P，令 M(P)=\max_{(i,j)\in P}a_{i,j}，则 F(x)=\min\limits_{P}M(P)。

由于往左走对 F(x) 函数的值没有影响，故只考虑上下右转移，符合无后效性，可以使用 DP 实现 F(x)：

状态设计

设 f_{i,j} 表示从起点 (1,1) 出发，只经过权值大于 x 的格子，到达 (i,j) 的所有路径中，路径上经过的格子权值的最大值的最小可能值。若不可达，则 dp_{i,j}=+\infty。\ 设 v_{i,j} 表示从起点 (1,1) 出发，只经过权值大于 x 的格子，可否到达 (i,j)，可以则为 \text{true}，不能则为 \text{false}（这是为方便转移准备的，不然在转移时分不清究竟是 a_{i,j}<x 还是没有路径导致的不可达。所以在转移到当前行时，v_{i,j}=[a_{i,j}\ge x]）。

初始化

将 (1,0) 设为可达（v_{1,0}=\text{true}，设计为从 (1,0) 开始可以简化第一列的转移）。

DP 过程

从 1 到 n 枚举 j：

  • 根据 (1,j) 是否合法设定 v_{1,j} 的值（v_{1,j}=[a_{1,j}\ge x]）。
  • 根据 (2,j) 是否合法设定 v_{2,j} 的值（v_{2,j}=[a_{2,j}\ge x]）。
  • 将 (1,j) 和 (2,j) 均设为不可达（f_{1,j}=f_{2,j}=+\infty）。
  • 水平转移：
    • 第一行：如果 (1,j-1) 可达且 (1,j) 合法（v_{1,j-1}=v_{1,j}=\text{true}），则转移 f_{1,j}=\max(f_{1,j-1},a_{1,j})。
    • 第二行：如果 (2,j-1) 可达且 (2,j) 合法（v_{2,j-1}=v_{2,j}=\text{true}），则转移 f_{2,j}=\max(f_{2,j-1},a_{2,j})。
  • 若 (1,j) 和 (2,j) 均合法（v_{1,j}=v_{2,j}=\text{true}），垂直转移：
    • 若 (1,j) 和 (2,j) 均可达（f_{1,j}\ne+\infty,f_{2,j}\ne+\infty），上下相互转移：
    • 若 f_{1,i}<f_{2,i}，从上往下转移：f_{2,j}=\max(a_{2,j},\min(f_{1,j},f_{2,j}))。
    • 若 f_{1,i}>f_{2,i}，从下往下转移：f_{1,j}=\max(a_{1,j},\min(f_{2,j},f_{1,j}))。
    • 若 (1,j) 可达，(2,j) 不可达（f_{1,j}\ne+\infty,f_{2,j}=+\infty），从上往下转移：
    • 若 (1,j) 不可达，(2,j) 可达（f_{1,j}=+\infty,f_{2,j}\ne+\infty），从下往上转移：
  • 根据 (1,j) 是否可达设定 v_{1,j} 的值（v_{1,j}=[f_{1,j}\ne+\infty]）。
  • 根据 (2,j) 是否可达设定 v_{2,j} 的值（v_{2,j}=[f_{2,j}\ne+\infty]）。

最后返回 f_{2,n}。

最朴素的暴力做法即为：

从 1 到 2n 枚举 l：

  • 如果 F(l)\ne+\infty，\text{Ans}\gets\text{Ans}+(2n-F(l)+1)。
  • 否则，显然再加大限制也不可能到达了，直接退出。

但是暴力做法会 TLE。考虑优化：

考虑一种情况：k\notin a_{i,j}。\ 在这种情况下，由于 F(k+1) 的限制（从只能走 a_{i,j}\ge k 到只能走 a_{i,j}\ge k+1，a_{i,j}=k 不能走了）对从 (1,1) 走到 (2,n) 没有影响，F(k)=F(k+1)。所以，在这种情况下，计算 F(k) 是不必要的。\ 因此，只需在输入时将每个数记录进一个数组 p（为方便计算，p_0=0），排序，去重，并从小到大枚举：

  • 如果 F(p_i)\ne+\infty，\text{Ans}\gets\text{Ans}+(p_i-p_{i-1})(2n-F(p_i)+1)。

  • 否则，显然再加大限制也不可能到达了，直接退出。

为什么？

因为 F(l)（即最小需要的 r）的值，只会在 l 经过某个格子的权值 a_{i,j} 时才可能发生变化。当 l 在区间 (p_{i-1}, p_i] 内增加时，可以通行的格子集合没有变化，因此最小需要的 r 也不变。所以，对于这个区间内的所有 l，它们对应的合法 r 范围是相同的，都是从 F(p_i) 到 2n。因此，这一整段 l 贡献的通行卡数量就是区间长度 (p_i - p_{i-1}) 乘以可选的 r 的数量 (2n - F(p_i) + 1)。

程序实现

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int T,n,a[3][200005],kn[400005],cnt,dp[3][200005];
bool v[3][200005];
long long ans;
int bfs(int k){ // 用 DP 实现的 F(x) 函数
    v[1][0]=true; // 初始化
    for(int i=1;i<=n;i++){
        dp[1][i]=dp[2][i]=-1;
        v[1][i]=(a[1][i]>=k);
        v[2][i]=(a[2][i]>=k);
        if(v[1][i-1] && v[1][i])dp[1][i]=max(dp[1][i-1],a[1][i]);
        if(v[2][i-1] && v[2][i])dp[2][i]=max(dp[2][i-1],a[2][i]); // 水平转移
        if(v[1][i] && v[2][i]){ // 垂直转移
            if(dp[1][i]>=0 && dp[2][i]>=0){
                if(dp[1][i]<dp[2][i])
                    dp[2][i]=max(a[2][i],min(dp[1][i],dp[2][i]));
                if(dp[1][i]>dp[2][i])
                    dp[1][i]=max(a[1][i],min(dp[2][i],dp[1][i]));
            }
            else if(dp[1][i]>=0)dp[2][i]=max(a[2][i],dp[1][i]);
            else if(dp[2][i]>=0)dp[1][i]=max(a[1][i],dp[2][i]);
        }
        if(dp[1][i]==-1)v[1][i]=false;
        if(dp[2][i]==-1)v[2][i]=false; // 更新可达性
    }
    return dp[2][n];
}
int main(){
    scanf("%d",&T); // 多测
    while(T--){
        cnt=ans=0;
        scanf("%d",&n);
        for(int i=1;i<=2;i++)for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            kn[++cnt]=a[i][j]; // 存入数组
        }
        sort(kn+1,kn+cnt+1); // 排序
        for(int i=1,r;i<=cnt;i++){
            if(kn[i]==kn[i-1])continue; // 类似于去重操作
            r=bfs(kn[i]); // 得到 r 的下限
            if(r!=-1)ans+=1LL*(kn[i]-kn[i-1])*(2*n-r+1); // 计算答案
            else break;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

AC 记录：Record