Hi Guys,
I was trying to solve the plates problem from the last kickstart round. I tried one approach which is not failing i dont know where the mistake is. Please help me resolving this.
Approach :
1. Processing from the last stack of plates.
2. In the last stack the max beauty i can get will be the K plates from that stack, so i'll copy it. At this point, if my P value is 1 to K, it is straightway the no of plates in the stack.
3. Now i'll come to the N-1th stack, now i'll compare with previously processed one and i'll process the different combinations of plates. Ex : If i want one plate, i can either take it from the current stack(N-1) or check the prev calculated and update the current result. This process goes on.
4. Step 3 will be going on till i'm on the 1st stack.
5. When i'm in the first stack i'll have the best beauties of picking up the (N * K) plates.
This is the approach i tried and it is failing. Please help me to rectify it. Thanks in advance
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Round_A_Plates {
public static void main(String[] args) {
FastReader reader = new FastReader();
int T = Integer.parseInt(reader.nextLine());
int cases = 1;
while(T > 0) {
String[] input = reader.nextLine().split(" ");
int N = Integer.parseInt(input[0]);
int K = Integer.parseInt(input[1]);
int P = Integer.parseInt(input[2]);
int[][] stackOfPlates = new int[N][K];
for(int i = 0;i < N;i++) {
input = reader.nextLine().split(" ");
for (int j = 0; j < K;j++)
if(j == 0)
stackOfPlates[i][j] = Integer.parseInt(input[j]);
else
stackOfPlates[i][j] = stackOfPlates[i][j - 1] + Integer.parseInt(input[j]);
}
int[] prev = null;
for(int i = N - 1, plates = 1;i >= 0;i--, plates++) {
int[] res = new int[plates * K];
if(i == N - 1) {
System.arraycopy(stackOfPlates[i], 0, res, 0, plates * K);
prev = res;
}
else{
for(int j = 0, k = 0;j < K;j++) {
res[j] = Math.max(stackOfPlates[i][j], prev[j]);
for(k = 0;k < prev.length;k++) {
int currentVal = stackOfPlates[i][j] + prev[k];
int total = j + k + 1;
res[total] = (total < prev.length) ? Math.max(prev[total], currentVal) : Math.max(res[total] , currentVal);
}
}
prev = res;
}
}
System.out.println("Case #" + cases + ": " +prev[P - 1]);
T--;
cases++;
}
}
static class FastReader
{
// Reader class
}
}