P10119 『STA - R4』踱步

Noby_Glds · 2024-02-01 22:11:02 · 题解

首先对 a,b 做前缀和，分别表示为 s_{0},s_1。

设 f_{i,k,op} 表示对于前 i 个位置，强制在 i+1 分钟初踱步，总共踱步 k 次，且第 i 分钟在屋内（op=0）或屋外（op=1）的最大答案。

显然我们有以下转移方程：

移项可得：

滚动数组滚掉一维：

分情况讨论：

i-j\leq T

此时转移区间的范围是 [i-T,i-1]，且联系到区间求最值，我们很容易想到单调队列优化，别忘了把答案加上 P。

i-j>T

转移区间为 [k-1,i-T-1]，注意到左端点固定，右端点递增，只需要开一个变量维护最大值。

最后，op 有两个取值，记得要做两次转移。

#include<bits/stdc++.h>
#define int long long
#define N 200010
using namespace std;
int id,T,n,m,t,p;
int f[N][2],s[N][2],g[N][2],q[N];
int get(int x,int y){return f[x][y^1]-s[x][y];}
void work(int pos,int op){
    int now=-1e18,l=1,r=1;
    q[1]=pos-1;
    for(int i=pos;i<=n;i++){
        if(i-t-1>=pos-1) now=max(now,get(i-t-1,op));
        while(l<=r&&q[l]<i-t) l++;
        g[i][op]=max(now,get(q[l],op)+p)+s[i][op];
        while(l<=r&&get(i,op)>=get(q[r],op)) r--;
        q[++r]=i;
    }
} 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>id>>T;
    while(T--){
        cin>>n>>m>>t>>p;
        for(int i=1;i<=n;i++){
            cin>>s[i][0]>>s[i][1];
            s[i][0]+=s[i-1][0],s[i][1]+=s[i-1][1];
            f[i][0]=s[i][0],f[i][1]=s[i][1];
        } 
        int ans=max(s[n][0],s[n][1]);//不踱步
        for(int i=1;i<n;i++) ans=max(ans,max(f[i][0]+s[n][1]-s[i][1],f[i][1]+s[n][0]-s[i][0]));//一次踱步
        for(int pos=2;pos<=m;pos++){
            work(pos,0),work(pos,1);
            for(int i=pos;i<n;i++){
                f[i][0]=g[i][0],f[i][1]=g[i][1];
                ans=max(ans,max(f[i][0]+s[n][1]-s[i][1],f[i][1]+s[n][0]-s[i][0]));
            } 
        }
        cout<<ans<<endl;
    }
    return 0;
}