题意:
有
题解:
首先,
但是,这样转移的时间复杂度为
考虑优化,进一步发现
每一次转移如果
需要注意的一点是,要先把所有dp值算出来之后再一一更新。
#include<bits/stdc++.h>
using namespace std;
const int Maxn=6,Maxm=1e5+50;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
int m,n,k,l;
ll sum[Maxn][Maxm],ans=INF;
struct node
{
int pos;ll val;
node(int pos=0,ll val=0):pos(pos),val(val){}
};
int head[Maxn][Maxn],tail[Maxn][Maxn];
node q[Maxn][Maxn][Maxm];
ll f[Maxm][Maxn];
int main()
{
scanf("%d%d%d%d",&m,&n,&k,&l);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%lld",&sum[i][j]);
sum[i][j]+=sum[i][j-1];
}
if(n==1)
{
printf("%lld\n",sum[1][m]);
return 0;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
q[i][j][head[i][j]=tail[i][j]=0]=node(0,-k);
for(int t=1;t<=m;t++)
{
for(int i=1;i<=n;i++)
{
ll id=0;
for(int j=1;j<=n;j++)
{
if(j==i)continue;
while(q[i][j][head[i][j]].pos<t-l)head[i][j]++;
if(!id||f[t][i]>q[i][j][head[i][j]].val)id=j,f[t][i]=q[i][j][head[i][j]].val;
}
f[t][i]+=((ll)k+sum[i][t]);
if(t==m)ans=min(ans,f[t][i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i==j)continue;
ll tmp=f[t][i]-sum[j][t];
while(head[j][i]<=tail[j][i]&&q[j][i][tail[j][i]].val>=tmp)tail[j][i]--;
q[j][i][++tail[j][i]]=node(t,tmp);
}
}
}
printf("%lld\n",ans);
}