仔细理解题意之后,发现段可以不是连续的。
那么就好办多了。
有$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;
}
最后一次更新于2021-02-04
0 条评论