Vijos 1243 生产产品


https://vijos.org/p/1243
在经过一段时间的经营后,dd_engi的OI商店不满足于从别的供货商那里购买产品放上货架,而要开始自己生产产品了!产品的生产需要M个步骤,每一个步骤都可以在N台机器中的任何一台完成,但生产的步骤必须严格按顺序执行。由于这N台机器的性能不同,它们完成每一个步骤的所需时间也不同。机器i完成第j个步骤的时间为T[i,j]。把半成品从一台机器上搬到另一台机器上也需要一定的时间K。同时,为了保证安全和产品的质量,每台机器最多只能连续完成产品的L个步骤。也就是说,如果有一台机器连续完成了产品的L个步骤,下一个步骤就必须换一台机器来完成。现在,dd_engi的OI商店有史以来的第一个产品就要开始生产了,那么最短需要多长时间呢?
某日Azuki.7对跃动说:这样的题目太简单,我们把题目的范围改一改
对于菜鸟跃动来说,这是个很困难的问题,他希望你能帮他解决这个问题

格式

输入格式

第一行有四个整数M, N, K, L
下面的N行,每行有M个整数。第I+1行的第J个整数为T[J,I]。

输出格式

输出只有一行,表示需要的最短时间。

样例1

样例输入1

3 2 0 2
2 2 3
1 3 1

样例输出1

4

限制

1s

提示

对于50%的数据,N<=5,L<=4,M<=10000
对于100%的数据,N<=5, L<=50000,M<=100000

来源

第一届“OI商店杯” dd_engi原创题目

https://sea96.github.io/2017/02/25/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%9A%84%E5%90%84%E7%A7%8D%E4%BC%98%E5%8C%96/
题意:产品的生产需要m(105)个步骤,每个步骤可以在n(5)个机器中任何一台完成,机器i完成第j个步骤的时间为ai,j。把半成品从一台机器上搬到另一台机器上也需要一定的时间k,每台机器最多只能连续完成产品的l(5104)个步骤,问最短需要多长时间。
题解:朴素的动态规划的算法:定义dp[i][j]表示前i个步骤,最后一段步骤用第j个机器完成,sum[i][j]表示前i个步骤用第j个机器完成的时间。状态转移方程:
dp[i][j]=min{dp[t][p]+(sum[i][j]sum[t][j])+k},(jp,itl)
时间复杂度:O(n2ml)
把方程式变形得:
dp[i][j]=min{dp[t][p]sum[t][j]}+sum[i][j]+k,(jp,itl)
发现括号内的式子是根据t决定的(枚举pj),所以可以用单调队列维护一个单调递增的序列进行优化,时间复杂度:O(n2m)
http://www.cnblogs.com/MashiroSky/p/5950893.html
  一个产品的生产有m个步骤,一共n个机器人。机器人i完成步骤j的时间为T[i][j],每次当产品从一个机器人那里移动到另一个机器人那里需要时间K,每个机器人不能持续工作L个步骤。问最少能在多少时间内完成。

  看起来题目变量非常多,其实想一想就能列出dp方程:f[i][j]表示第i个机器人完成第j个步骤,一共完成前j个步骤所需要的最短时间;s[i][j]表示第i个机器人做完前j个步骤所需要的时间,那么:
f[i][j]=min(f[k][l]+s[i][j]s[i][l]+K)

  其中k[1,n]kjl[jL,j1]
  但是这样的话复杂度有点高。。我们发现n的范围只有5,我们可以从这里下手解决问题。如果对单独的一个机器人1号考虑,将dp方程转换一下:
f[i][j]=min((f[1][l]s[i][l])+s[i][j]+K)

  我们发现括号里的东西与j无关,可以用单调队列维护,所以我们开n个单调队列进行维护,问题就解决了。
int s[10][maxn],l[10],r[10],q[10][maxn],p[10][maxn],f[10][maxn];
int n,m,K,L;
 
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("%d",&s[i][j]),s[i][j]+=s[i][j-1];
    for (int i=1;i<=n;i++) l[i]=r[i]=1,q[i][1]=0,p[i][1]=0; 
    for (int j=1;j<=m;j++) {
        for (int i=1;i<=n;i++) {
            while (l[i]<=r[i] && p[i][l[i]]<j-L) l[i]++;
            f[i][j]=q[i][l[i]]+s[i][j]+K;
        }
        for (int i=1;i<=n;i++)
            for (int k=1;k<=n;k++) if (k!=i) {
                    while (l[k]<=r[k] && q[k][r[k]]>=f[i][j]-s[k][j]) r[k]--;
                    q[k][++r[k]]=f[i][j]-s[k][j];
                    p[k][r[k]]=j;
                }
    }
    int ans=inf;
    for (int i=1;i<=n;i++) ans=min(ans,f[i][m]);
    printf("%d",ans-K);
    return 0;
}
https://blog.csdn.net/hahalidaxin/article/details/51017626
       单调队列优化DP。

       设f[i][j]表示考虑到第i个步骤,且i步骤由j完成时的最小时间。有转移式:

        f[i][j]=min{f[k][p]-sum[k][j]}+sum[i][j],i-L<=k<=i-1

       括号内的部分可以用n个单调队列维护。a[][]为辅助数组,

   a[i][j]=min{f[i][k]}-sum[i][j]+K,1<=k<=m

   表示f[i][j]时括号中可以取到的最小值,单调队列j维护区间[i-L,i-1]内a[][j]的最小值。

       注意单调队列写法。
https://blog.csdn.net/XY20130630/article/details/51821751
设 f[i][j]f[i][j] 表示第 jj 个步骤由 ii 完成,而第 j+1j+1 个步骤不由 ii 完成。

f[i][j]=minnx=1(x≠i)minj−1Max(y=j−l,0)f[k][l]+∑m=l+1jT[i][m]
可用单调队列和前缀和进行优化

http://www.voidcn.com/article/p-pcchalxy-md.html
由于理论性的东西已经学过了,知道这是个dp+单调队列。可第一次编还是编了好久。
首先,很容易写出动态转移方程:f(i,j)=min( min( f(p,i) ) + sum(i,j) - sum(i,k) +val) ,i>k>i-l+1,m>p>0 && p!=i
由于m很小,小于6,所以,这个方程的主要优化在于寻找外层的min
而单调队列的方程为:f(x)= opt( cost[i] ) bound[x] <=i<x;
将动态转移方程化简得:f(i,j)=min( min( f(p,i) ) - sum(i,k) ) + sum(i,j)+val ,i>k>i-l+1,m>p>0 && p!=i
这样就可以用单调队列实现了。



Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts