首页 > 代码库 > Vijos 1243 生产产品 （优先队列优化的动态规划）

Vijos 1243 生产产品 （优先队列优化的动态规划）

2024-07-06 22:02:55   225人阅读

题意：中文题。不说了。

注意一些地方，机器的执行过程是没有顺序的，而且每个机器可以用多次。第一次执行的机器不消耗转移时间K。

 

用dp[i][j]表示第i个机器完成第j个步骤的最短时间，sum[j][i]表示第i个机器完成前j个步骤的时间。

比较容易想到一个朴素的状态转移方程：

dp[i][j]=min{dp[k][j‘]+sum[j][i]-sum[j‘][i]}+K  (j-j‘<l),(i!=k)

这里状态是O（n*m)，转移是O(n*l)，一定会超时，需要优化。

方程变形得dp[i][j]=min{dp[k][j‘]-sum[j‘][i]}+sum[j][i]+K

在这里如果把k和i看作常数，那么dp[k][j‘]-sum[j‘][i]是一个只和j‘量。由于k和i比较小，我们完全可以枚举k和i的所有情况，我们定义该量为opt[i][k]，我们只需要维护j-l到j这段范围内这个量的最小值即可。这里使用二维的优先队列来解决。转移部分优化成O（n）。总时间可以接受。

 

笔者曾经一度被初始化部分卡住，所以这里着重解释一下初始化部分的写法。

当j=1时，j唯一可能转移而来的状态就是j=0，所以首先我们要在队列里存入所有队列里存入j=0的下标，但这样还不够，还要更新j=0的状态，j=0时opt[i][k]这个变量是等于0，所以对应opt[i][k]=dp[k][0]+sum[0][i]，需要把dp[k][0]和sum[0][i]都初始化为0。其他情况下，dp[i][j]都初始化为INF。

可以这么写：

    memset(dp,0x7f,sizeof(dp));
    for(int i=1; i<=n; ++i)
        dp[i][0]=0;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            dq[i][j].push_back(0);

或者是下标j从0开始枚举，这样就包含了将j=0存入队列的部分，而初始化j=0的状态还是要自己来写。


维护队首和队尾的部分，要一次性全部完成，不能一次维护一个。

最后要注意的一个地方就是第一个机器是不花费转移机器的时间的，所以时间里要减去一个K。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<deque>
using namespace std;
int time[100005][6];
int dp[6][100005];
deque<int> dq[6][6];
int calc(int i,int j,int k)
{
    return dp[k][j]-time[j][i];
}
int main()
{
    int m,n,K,l;
    scanf("%d%d%d%d",&m,&n,&K,&l);
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            int t;
            scanf("%d",&t);
            time[j][i]=time[j-1][i]+t;
        }
    }
    int ans=0x7fffffff;
    memset(dp,0x7f,sizeof(dp));
    for(int i=1; i<=n; ++i)
        dp[i][0]=0;
    for(int j=0; j<=m; ++j)
    {
        for(int i=1; i<=n; ++i)
            for(int k=1; k<=n; ++k)
                if(i!=k) while(!dq[i][k].empty()&&(j-dq[i][k].front())>l) dq[i][k].pop_front();
        for(int i=1; i<=n; ++i)
            for(int k=1; k<=n; ++k)
                if(i!=k)
                {
                    int a=0,b=0;
                    if(!dq[i][k].empty()) a=calc(i,dq[i][k].front(),k);
                    b=time[j][i]+K;
                    dp[i][j]=min(dp[i][j],a+b);
                }
        for(int i=1; i<=n; ++i)
            for(int k=1; k<=n; ++k)
                if(i!=k)
                {
                    while(!dq[i][k].empty()&&(calc(i,dq[i][k].back(),k)>=calc(i,j,k))) dq[i][k].pop_back();
                    dq[i][k].push_back(j);
                }
    }
    for(int i=1; i<=n; ++i)
        ans=min(ans,dp[i][m]);
    printf("%d\n",ans-K);
    return 0;
}
View Code

 

 

 

 


联系
我们