仔细理解题意之后,发现段可以不是连续的

那么就好办多了。

有$f_i$表示时间$i$下未在任意一处工厂买机器人的最大收益。

$f_i=\max\limits_{k\in[1,p],j\in[0,n-1]}\{f_{i-k}+g_{i,j}-g_{i-k,j-k}-cost_{j-k}\}$(未拐弯)

其中$g_{i,j}$表示在时间$i$下,到达$j$获得的前缀收益和。

之后优化不优化无所谓。

用单调队列优化的话要注意对应。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=1005;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int g[N][N],cost[N],q[N][N],l[N],r[N],f[N],t[N][N];
int main()
{
    int n,m,p;qr(n),qr(m),qr(p);
    for(int i=1;i<=n;i++)
    {
        int w=i%n;
        for(int j=1;j<=m;j++)
            qr(g[j][w]);
    }
    for(int j=1;j<=m;j++)
        for(int i=0;i<n;i++)
            g[j][i]+=g[j-1][(i-1+n)%n];
    for(int i=0;i<n;i++)qr(cost[i]);
    memset(f,0xcf,sizeof(f));f[0]=0;
    for(int i=0;i<n;i++)l[i]=r[i]=1,q[i][1]=-cost[i];
    for(int i=1;i<=m;i++)
    {
        for(int j=0;j<n;j++)
        {
            int id=((j-i)%n+n)%n;
            while(l[id]<=r[id]&&t[id][l[id]]+p<i)++l[id];
            if(l[id]<=r[id])
                f[i]=max(f[i],q[id][l[id]]+g[i][j]);
        }
        for(int j=0;j<n;j++)
        {
            int id=((j-i)%n+n)%n,tmp=f[i]-g[i][j]-cost[j];
            while(l[id]<=r[id]&&tmp>=q[id][r[id]])--r[id];
            q[id][++r[id]]=tmp;
            t[id][r[id]]=i;
        }
    }
    qw(f[m]);puts("");
    return 0;
}