CF2275E Repentance Is Already on the Way 题解

· · 题解

考虑如何区。

这个区题我怎么做了半个小时。

这个人的行走轨迹大概是这样：

图画的不好，将就看吧 /kel。

那么一定存在一个位置，也就是 \text{ed}（终点）所在的那一列（令一组 a_i 和 b_i 同处在第 i 列），可以将整个轨迹划分成图上蓝色和绿色两段。

我们枚举当前这一列 i，考察维护一个前缀和一个后缀和处理蓝色和绿色的部分，算一下即可。

具体的，初值 s_1 = 0 和 t_n = 0，转移分别是 s_i = s_{i-1} + val_{a_{i-1} \to b_{i-1}} + val_{b_{i-1} \to a_i}，以及 t_i = t_{i+1} + val_{a_i \to b_{i+1}} + val_{a_{i+1} \to b_i}。结合图片更好理解。

答案就是 \max_{i=0}^{n} s_i + t_i + val_{a_n \to b_n}，后面这个 val_{a_n \to b_n} 也可以在 t 里面处理上。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
LL T,n,a[N],b[N],s[N],t[N]; 
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    T=read();
    while(T--){
        n=read();
        for(int i=1;i<=n;i++)a[i]=read();
        for(int i=1;i<=n;i++)b[i]=read();
        s[1]=0,t[n]=0;
        for(int i=2;i<=n;i++)
            s[i]=s[i-1]+(1+(a[i-1]==b[i-1]))+(1+(b[i-1]==a[i]));
        for(int i=n-1;i>=1;i--)
            t[i]=t[i+1]+(1+(a[i]==b[i+1]))+(1+(a[i+1]==b[i]));
        LL ans=0;
        for(int i=0;i<=n;i++){
            LL res=s[i]+t[i]+(1+(a[n]==b[n]));
            ans=max(ans,res);
        }
        cout<<ans<<"\n"; 
    }
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！