题解 P8983 【「DROI」Round 1 失控】

· · 题解

闲话：出题人曾经转移那部分的问题抽象之后丢到洛谷讨论区里问过，我当时顺手就回答了一下然后 std 用了我的做法，没想到这次遇上了！

全新出题方式，学到了！！1

但是这个题是有性质的，可以做到更优的复杂度。

为了方便考虑，我们加入操作 0 满足 A_0=0，B_0=0 表示不操作。

那么每行我们都必须选择一个操作进行且不能进行连续两次非零操作。

考虑 dp，记 f_{i,0/1,j} 表示当前考虑了前 i 行，前 i-1 行已经确定合法，0/1 表示最后两行中非零操作是哪一行，使用的是第 j 个操作。（需要注意一下两行都为零操作的情况）

转移即考虑 i+1 行进行什么操作，然后检验第 i 行是否合法。

若暴力枚举下一行进行哪个操作，检验是否合法，时间复杂度 \mathcal O(nmk^2)。

考虑优化，首先若非零操作在最后一行，那么下一行只能进行操作 0，暴力转移即可，时间复杂度 \mathcal O(nmk)。

那么现在剩下的情况就是最后一行为操作 0，倒数第二行操作为 j。

考虑对于每个下一个进行的操作快速找出哪些 j 是合法的，对于第 i 行的每个元素 G_{i,x} 都需要满足 \vert G_{i,j} - G_{i-1,p_j} \vert > C 且 \vert G_{i,j} - G_{i+1,q_j} \vert > C，因此第 i-1 行和第 i+1 行我们都可以得到一个区间，当加的数在这个区间内时满足条件。

于是条件变为两行加的数不能都不在区间里，我们枚举 i+1 行进行了什么操作，若加的数在对应区间内，那么没有限制；否则不在区间内，那么 i-1 行操作的数必须在区间中。

可以对于每个操作维护出 i-1 行加数区间的交，时间复杂度 \mathcal O(nmk)。

最后，对于 i+1 每个操作能转移的的位置是按照操作的加数 A_i 排序后的一段区间，离散化后查询区间最小值即可。

时间复杂度 \mathcal O(nmk+n\cdot\operatorname{rmq}(k))。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=55;
const int M=305;
const int K=2e3+5;

int n,m,k,C,a[N][M],p[M],q[M],A[K],B[K],dp[N][2][K],pos[K],b[K],st[11][K],Log[K];

signed main() {
    ios::sync_with_stdio(false),cin.tie(0);
    cout.precision(10),cout.setf(ios::fixed);

    cin>>n>>m>>k>>C;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cin>>a[i][j];
        }
    }
    for (int i=1;i<=m;i++) {
        cin>>p[i];
    }
    for (int i=1;i<=m;i++) {
        cin>>q[i];
    }
    for (int i=1;i<=k;i++) {
        cin>>A[i];
        b[i]=A[i];
    }
    for (int i=1;i<=k;i++) {
        cin>>B[i];
    }
    b[k+1]=0;
    sort(b+1,b+k+2);
    int cnt=unique(b+1,b+k+2)-b-1;
    for (int i=0;i<=k;i++) {
        pos[i]=lower_bound(b+1,b+cnt+1,A[i])-b;
    }
    for (int i=2;i<=cnt;i++) {
        Log[i]=Log[i/2]+1;
    }

    memset(dp,0x3f,sizeof(dp));
    for (int i=0;i<=k;i++) {
        dp[1][i>0][i]=B[i];
    }
    for (int i=2;i<=n;i++) {
        for (int j=1;j<=k;j++) {
            dp[i][0][j]=dp[i-1][1][j];
        }
        vector<pair<int,int>>lim(k+1,make_pair(-(int)1e9,(int)1e9));
        if (i>2) {
            for (int j=1;j<=m;j++) {
                int L1=(a[i-1][j]-C)-a[i-2][p[j]],R1=(a[i-1][j]+C)-a[i-2][p[j]];
                int L2=(a[i-1][j]-C)-a[i][q[j]],R2=(a[i-1][j]+C)-a[i][q[j]];
                for (int t=0;t<=k;t++) {
                    if (A[t]<L2||A[t]>R2) {
                        lim[t].first=max(lim[t].first,L1);
                        lim[t].second=min(lim[t].second,R1);
                    }
                }
            }
        }
        for (int j=1;j<=cnt;j++) {
            st[0][j]=1e9+7;
        }
        for (int j=0;j<=k;j++) {
            st[0][pos[j]]=min(st[0][pos[j]],dp[i-1][0][j]);
        }
        for (int j=1;j<11;j++) {
            for (int t=1;t<=cnt;t++) {
                st[j][t]=min(st[j-1][t],st[j-1][t+(1<<(j-1))]);
            }
        }
        for (int x=0;x<=k;x++) {
            bool flag=1;
            if (i<n&&x) {
                for (int j=1;j<=m;j++) {
                    if (abs(a[i][j]+A[x]-a[i-1][p[j]])>C&&abs(a[i][j]+A[x]-a[i+1][q[j]])>C) {
                        flag=0;
                        break;
                    }
                }
            }
            if (!flag) {
                continue;
            }
            int l=lower_bound(b+1,b+cnt+1,lim[x].first)-b;
            int r=upper_bound(b+1,b+cnt+1,lim[x].second)-b-1;
            if (l<=r) {
                int k=Log[r-l+1];
                int mn=min(st[k][l],st[k][r-(1<<k)+1]);
                dp[i][x>0][x]=min(dp[i][x>0][x],mn+B[x]);
            }
        }
    }
    int ans=1e9+7;
    for (int i=0;i<=k;i++) {
        ans=min(ans,min(dp[n][0][i],dp[n][1][i]));
    }
    cout<<ans<<"\n";

    return 0;
}