题解：P15361 「WYZOI R2」拜年

原题：P15361

算法分析

若不存在从 $(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_{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 过程

枚举 $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$），从上往下转移：
    • $f_{2,j}=\max(a_{2,j},\min(f_{1,j},f_{2,j}))$。
  • 若 $(1,j)$ 不可达，$(2,j)$ 可达（$f_{1,j}=+\infty,f_{2,j}\ne+\infty$），从下往上转移：
    • $f_{1,j}=\max(a_{1,j},\min(f_{2,j},f_{1,j}))$。
• 根据 $(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)$。
• 否则，显然再加大限制也不可能到达了，直接退出。

考虑一种情况：$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)$。

程序实现

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#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