Solution
- The problem can be solved using dynamic programming. Since there are $N$ minutes and $M$ customers, the dp requires an $N \times (M+1)$ matrix, that is $dp[N][M+1]$
- We know that if a customer receives the item that he/she ordered in the $i^{th}$ minute, he/she will spend the next minute, that is, the $(i+1)^{th}$ minute, consuming the item.
- Since, in the $1^{st}$ minute, no customer is consuming any item, the first row of $dp$ is initialized with the elements corresponding to the first row of $a$ and the $M^{th}$ element in the first row is set to 0.
- Since, in the $2^{nd}$ minute, the orders of the customers whose position is not $pos$ can be fulfilled, the revenue which can be generated by fulfilling the order of the $j^{th}$ customer is $a[1][j]+max(dp[0])$. Therefore, we set $dp[1][j] = a[1][j]+max(dp[0])$ for all $0 \le j \lt N$ and $j \ne pos$.
- Since the customer at $pos$ is busy in consumption if his/her order was fulfilled in the first minute, the second largest element in $dp[0]$ is added to $a[1][pos]$. Therefore, we set $dp[1][pos] = a[1][j]+secondmax(dp[0])$
- $dp[1][M]$ is set to $max(dp[0])$. This is done with the assumption that no order is fulfilled in the $1^{st}$ minute. It is necessary for all $dp[i][M]$ to be set to $max(dp[i-1])$, where $0 \lt i \lt N$, keeping in mind the edge case where $M = 1$.
- The above three steps is repeated for all the remaining rows in $dp$. That is for all $0 \lt i \lt N$ and $0 \le j \lt M$
- $dp[i][j] = a[i][j]+max(dp[i-1])$ if $j \ne pos$
- $dp[i][pos] = a[i][j]+secondmax(dp[i-1])$ if $j = pos$
- $dp[i][M] = max(dp[i-1])$
Implementation using C++
#include <cstdio>
using namespace std;
int main() {
int t, n, m, i, j;
scanf("%d", &t);
int a[100][100];
int dp[100][101];
int m1, m2, pos, ans;
while(t--) {
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
scanf("%d", &a[i][j]);
/*
First row of dp is initialised to corresponding
elements of first row of a. The last element of
dp[0] is initalised to 0.
*/
for (i = 0; i < m; i++)
dp[0][i] = a[0][i];
dp[0][m] = 0;
/*
For all the rows, i from 1 to n-1, find the largest
and second largest element in dp[i-1] and keep note
of the position of the largest element.
Initialize all the elements of dp in the ith row
according to the follwing
dp[i][j] = a[i][j]+max(dp[i-1]) when j != pos
dp[i][pos] = a[i][j]+secondmax(dp[i-1]) when j == pos
dp[i][M] = max(dp[i-1])
*/
for (i = 1; i < n; i++) {
if (dp[i-1][0] > dp[i-1][1]) {
m1 = dp[i-1][0];
m2 = dp[i-1][1];
pos = 0;
}
else {
m1 = dp[i-1][1];
m2 = dp[i-1][0];
pos = 1;
}
for (j = 2; j < m; j++) {
if (dp[i-1][j] > m1) {
m2 = m1;
m1 = dp[i-1][j];
pos = j;
}
else if (dp[i-1][j] > m2)
m2 = dp[i-1][j];
}
for (j = 0; j < m; j++) {
if (j == pos)
dp[i][j] = m2+a[i][j];
else
dp[i][j] = m1+a[i][j];
}
dp[i][m] = m1;
}
/*
The maximum possible revenue is the
largest element in the last row of dp
*/
ans = dp[n-1][0];
for (i = 1; i <= m; i++)
if (dp[n-1][i] > ans)
ans = dp[n-1][i];
printf("%d\n", ans);
}
return 0;
}
Implementation using Java
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int t, n, m, i, j;
int a[][] = new int[100][100];
int dp[][] = new int[100][101];
int m1, m2, pos, ans;
t = scan.nextInt();
scan.nextLine();
while (t-- > 0) {
n = scan.nextInt();
m = scan.nextInt();
scan.nextLine();
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
a[i][j] = scan.nextInt();
scan.nextLine();
}
/*
First row of dp is initialised to corresponding
elements of first row of a. The last element of
dp[0] is initalised to 0.
*/
for (i = 0; i < m; i++)
dp[0][i] = a[0][i];
dp[0][m] = 0;
/*
For all the rows, i from 1 to n-1, find the largest
and second largest element in dp[i-1] and keep note
of the position of the largest element.
Initialize all the elements of dp in the ith row
according to the follwing
dp[i][j] = a[i][j]+max(dp[i-1]) when j != pos
dp[i][pos] = a[i][j]+secondmax(dp[i-1]) when j == pos
dp[i][M] = max(dp[i-1])
*/
for (i = 1; i < n; i++) {
if (dp[i-1][0] > dp[i-1][1]) {
m1 = dp[i-1][0];
m2 = dp[i-1][1];
pos = 0;
}
else {
m1 = dp[i-1][1];
m2 = dp[i-1][0];
pos = 1;
}
for (j = 2; j < m; j++) {
if (dp[i-1][j] > m1) {
m2 = m1;
m1 = dp[i-1][j];
pos = j;
}
else if (dp[i-1][j] > m2)
m2 = dp[i-1][j];
}
for (j = 0; j < m; j++) {
if (j == pos)
dp[i][j] = m2+a[i][j];
else
dp[i][j] = m1+a[i][j];
}
dp[i][m] = m1;
}
/*
The maximum possible revenue is the
largest element in the last row of dp
*/
ans = dp[n-1][0];
for (i = 1; i <= m; i++)
if (dp[n-1][i] > ans)
ans = dp[n-1][i];
System.out.println(ans);
}
}
}
Implementation using Python
for _ in range(int(input())):
n, m = map(int, input().split())
a = []
for i in range(0, n):
a.append(list(map(int, input().split())))
dp = []
for i in range(0, n):
temp = []
for j in range(0, m+1):
temp.append(0)
dp.append(temp)
# First row of dp is initialied with elements of first row of a
for i in range(0, m):
dp[0][i] = a[0][i]
# Last element of dp[0] is 0
dp[0][m] = 0
'''
For all the rows, i from 1 to n-1, find the largest
and second largest element in dp[i-1] and keep note
of the position of the largest element.
Initialize all the elements of dp in the ith row
according to the follwing
dp[i][j] = a[i][j]+max(dp[i-1]) when j != pos
dp[i][pos] = a[i][j]+secondmax(dp[i-1]) when j == pos
arr.append(max(dp[i-1]))
'''
for i in range(1, n):
maxpos = 0
m1 = dp[i-1][0]
m2 = dp[i-1][1]
if m2 > m1:
m2, m1 = m1, m2
maxpos = 1
for j in range(2, m):
if dp[i-1][j] > m1:
m2 = m1
m1 = dp[i-1][j]
maxpos = j
elif dp[i-1][j] > m2:
m2 = dp[i-1][j]
for j in range(0, m):
if j == maxpos:
dp[i][j] += m2+a[i][j]
else:
dp[i][j] += m1+a[i][j]
dp[i][m] = m1
# The maximum possible revenue is the largest element in the last row of dp
print(max(dp[n-1]))