Vijos 1243 生产产品[单调队列优化dp]-白红宇

Vijos 1243 生产产品[单调队列优化dp]

阅读量：6564 次

发布时间：2019-06-24

本文共 2121 字，大约阅读时间需要 7 分钟。

好吧...作为我A掉的第一道单调队列优化dp....在高中生的OJ上....而且我调了一个半小时样例....然后很神奇的1A = =...

诶这题果断比多校8的1005难啊...min里面的东西这么奇葩的...又 k 又 p 又 j 地...开始我以为只要一个队列, 搞了半天发现应该要N个队列... = =...写出来好神奇....

转移方程什么的详见代码吧....要碎了....

总结下:

形如 d[i] = min(f[k]) 的转移方程( k随i不降, f为可以根据 k 在常数时间内确定的唯一常数 ). 可以采用单调队列优化, 把求min的O(n)时间, 优化到O(1).

具体操作过程一般为:

设 k=[low, high].

1/ 把f[high]丢进deq. (维护deq, 若deq不为空, 先从尾部pop掉不符合单调的元素)

2/ 从首部找元素作为min(f[k]). (元素应满足k的范围, 即序号大于low, 不满足的pop掉).

代码:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            using namespace std;inline int Rint() { int x; scanf("%d", &x); return x; }inline int max(int x, int y) { return (x>y)? x: y; }inline int min(int x, int y) { return (x
            
             =(b);i--)#define REP(x) for(int i=0; i<(x); i++)typedef long long int64;#define INF (1<<30)const double eps = 1e-8;#define bug(s) cout<<#s<<"="<
             <<" "#define MAXN 7#define MAXM 100002#define MAXL 50002int d[MAXM][MAXN]; //d[i][j] 表示 第i个步骤由第j人完成所需的最短时间.// 转移方程: d[i][j] = min{ d[k][p]+cost[j][i]-cost[j][k] +K | k=[i-L, i-1], k>=1, p=[1, N], p!=j } .// 单调队列优化: d[i][j] = min{ d[k][p]-cost[j][k] | k=[i-L, i-1], k>=1, p=[1, N], p!=j } +cost[j][i] + K.// d[0][p] = -K;int cost[MAXN][MAXM]; // cost[i][j], 表示 第 i 个人, 完成 第 1~j 步骤 需要的时间和.int deq[MAXM][MAXN];int front[MAXN], tail[MAXN];int f[MAXM][MAXN]; //min(f)int main(){ memset(d, 0, sizeof(d)); memset(cost, 0, sizeof(cost)); int m=Rint(), n=Rint(), K=Rint(), L=Rint(); FOR(i, 1, n) { FOR(j, 1, m) { int t = Rint(); cost[i][j]=cost[i][j-1]+t; //前缀和 } } FOR(i, 1, n) { d[0][i] = -K; } //front = tail = 1; //下标从1开始 FOR(i, 1, n) { front[i] = tail[i] = 1; } FOR(i, 1, m) // d[i] = min(d[k][p]-cost[k]) + cost[i] + K { FOR(j, 1, n) { // 把 f[i-1] 丢进 deq f[i-1][j] = INF; FOR(p, 1, n) // min(d[k]-cost[k]) { if(p == j) continue; //f[i] = min(f[i], d[k][p]-cost[j][k]); //f[i] = min(f[i], d[i][p]-cost[j][i]); f[i-1][j] = min(f[i-1][j], d[i-1][p]-cost[j][i-1]); //由于 k<=i-1, 所以这里用 i-1, d[i][p]还没全算出来 } //bug(i-1);bug(j);bug(f[i-1][j])<

转载于:https://www.cnblogs.com/tclh123/archive/2012/08/20/6171729.html

你可能感兴趣的文章