题意:
因为是汉字的,就不解释了。
解题思路:
这是一道在论文上看的,但是我觉得那个论文解释的太不清楚了
所以我还是用自己的话来解释下
首先是f[i][j] 表示的是第i个机器处理了第j个任务时所耗费的时间
s[i][j]表示的是第i个机器连续处理1~j这些的任务消费时间总和(显然,可以直接在输入的时候就可以求出来)
那么可以得到一个公式
f[i,j] = min(f[p][h] - s[i][h]+k + s[i][j]) (i!=p && j-l<=h<i)
这里的时间复杂度很高,我们可以尝试用单调队列优化
可以发现min(f[p][h] - s[i][h]+k)这个里面的值是一个由k决定的常量值,那么我们可以把他丢到单调队列里面去求
另外由于p!=i,那么我们可以建立五个单调队列q[i],分别存储不是i的f[p][h] - s[i][h]+k
这样一来我们就将枚举h的时间复杂度优化了
另外,我要吐槽一下,VIJOS真心太坑了,后台的判题机环境都不一样
也不给你提示,I64和lld让我差不多纠结了一个小时,WTF
下面上代码:
#include<cstdio> #include<deque> #include<cstring> #include<iostream> using namespace std; #define LL long long #define maxn 6 #define maxm 200100 #define inf 0xFFFFFFF LL f[maxn][maxm]; LL s[maxn][maxm]; struct node { LL val; int pos; }; deque<node> q[maxn]; int m,n,k,l; //返回对列i中符合要求的头 LL gettop(int i,int j) { while(!q[i].empty() && q[i].front().pos < j-l) q[i].pop_front(); return q[i].front().val; } void q_insert(int i,LL v,int p) { node in; in.val=v; in.pos=p; while(!q[i].empty() && q[i].back().val >= in.val) q[i].pop_back(); q[i].push_back(in); } int main() { while(~scanf("%d%d%d%d",&m,&n,&k,&l)) { for(int i=1;i<=n;i++) q[i].clear(); for(int i=1;i<=n;i++) { s[i][0]=0; for(int j=1;j<=m;j++) { LL t; scanf("%I64d",&t); s[i][j]=s[i][j-1]+t; } } for(int i=1;i<=n;i++) { f[i][0] = 0; q_insert(i,0,0); } //然后开始后面的运算 for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) f[j][i] = gettop(j,i)+s[j][i]; for(int j=1;j<=n;j++) { LL t=inf; for(int h=1;h<=n;h++) { if(h==j) continue; if(t>f[h][i]) { t=f[h][i]; } } q_insert(j,t-s[j][i]+k,i); } } LL ans=inf; for(int i=1;i<=n;i++) if(ans>f[i][m]) ans=f[i][m]; printf("%I64d\n",ans); } return 0; }