题解：CF2122E Greedy Grid Counting

sqzyz · 2026-11-11 18:43:54 · 题解

对于多条贪心路径，显然只需要考虑拐弯最晚的。

考虑一条贪心路径等于最优路径的条件，令 b_i=a_{1,i}-a_{0,i+1}，那等价于 b_i>0，前缀 b_j 都 \le 0，从 i 开始统计前缀和始终非负。

现在要统计每个子矩形都满足条件的方案，把每个 b_i>0 看做一个分界点，这些点可能成为贪心路径的拐点，结合上面的条件，就是每一个分界点开始的一段，前缀和始终非负（两段都非负，拼起来一定非负，因此只考虑一段）。

一段出现负数后，因为到下一段之前始终都加不超过 0 的数，因此前缀和的值域是 O(k)，记录前缀和，每到一个新的位置枚举新的位置的 b_i 就能做到 3 次方。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=505;
const int mod=998244353;
int T,n,K;
int a[2][N];
int f[N][N],g[N];
int t[N][N<<1];
int calc(int p,int x){
    if(a[1][p]!=-1&&a[0][p+1]!=-1){
        if(a[1][p]-a[0][p+1]==x)return 1;
        return 0;
    }
    if(a[1][p]==-1&&a[0][p+1]==-1){
        return max(0,K-abs(x));
    }
    if(a[1][p]==-1){
        if(a[0][p+1]+x<1||a[0][p+1]+x>K)return 0;
        return 1;
    }
    if(a[1][p]-x<1||a[1][p]-x>K)return 0;
    return 1;
}
void solve(){
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    memset(t,0,sizeof(t));
    cin>>n>>K;
    for(int i=1;i<=n;i++)cin>>a[0][i];
    for(int i=1;i<=n;i++)cin>>a[1][i];
    for(int i=1;i<n;i++){
        for(int x=-K;x<=K;x++){
            t[i][x+K]=calc(i,x);
        }
    }
    g[0]=1;
    for(int i=0;i<n-1;i++){
        for(int k=0;k<=K;k++){
            for(int x=-K;x<=0;x++){
                if(k+x>=0)f[i+1][k+x]=(f[i+1][k+x]+1LL*t[i+1][x+K]*f[i][k]%mod)%mod;
            }
            for(int x=1;x<=K;x++){
                f[i+1][x]=(f[i+1][x]+1LL*t[i+1][x+K]*f[i][k]%mod)%mod;
            }
        }
        for(int x=-K;x<=0;x++){
            g[i+1]=(g[i+1]+1LL*g[i]*t[i+1][x+K]%mod)%mod;
        }
        for(int x=1;x<=K;x++){
            f[i+1][x]=(f[i+1][x]+1LL*g[i]*t[i+1][x+K]%mod)%mod;
        }
    }
    int ans=0;
    for(int k=0;k<=K;k++)ans=(ans+f[n-1][k])%mod;
    ans=(ans+g[n-1])%mod;
    if(a[0][1]==-1)ans=1LL*ans*K%mod;
    if(a[1][n]==-1)ans=1LL*ans*K%mod;
    cout<<ans<<"\n";
}
int main(){
    cin>>T;
    while(T--)solve();
    return 0;
}