Vijos1243:生产产品(单调队列优化dp)

时间:2022-01-23 19:09:56

传送门

题意:
n 个任务, m 个机器,每个机器完成每个任务都有特定的时间,任务必须依次完成,且一个机器只能连续完成 l 个任务,每次更换机器需要时间 k ,求完成所有任务的最短时间。
(n100000,m5)
题解:
首先, sum[i][j] 表示第 i 台机器完成前 j 项任务所需的时间, f[i][j] 表示完成了前 i 项任务,且第 i 项任务由第 j 台机器完成的最小时间,很容易写出转移方程:

f[i][j]=minx=ili1f[x][p]+sum[j][i]sum[j][x](pj)

但是,这样转移的时间复杂度为 O(nm2l)

考虑优化,进一步发现 n 很小,想办法从 n 下手优化:
每一次转移如果 j 确定,找的是 min(f[x][p]sum[j][x]) 。可以建立 n2 个关于 x 的单调队列,且保证 x,(f[x][p]sum[j][x]) 单调递增。每次取队首更新即可。选取出的最优解再按单调队列的规则去更新其他单调队列。时间复杂度 O(nm2)

需要注意的一点是,要先把所有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);
}