Hi, Can anyone please tell me a test case for which this code might fail? It gives WA.
short DPTable [1001][100][100], OxyArr [1024], NitArr[1024], WeightArr [1024], SumOxy, SumNit;
int main()
{
int Total, Oxy, Nit, CyCount;
scanf ("%d", &Total);
while (Total--)
{
scanf ("%d%d%d", &Oxy, &Nit, &CyCount);
for (int i = 0; i < CyCount; i++) scanf ("%d%d%d", &OxyArr[i], &NitArr[i], &WeightArr[i]);
memset (DPTable, -1, sizeof DPTable);
int Solution = numeric_limits <int>::max();
for (int i = 1; i <= CyCount; i++)
{
DPTable [i-1][0][0] = 0;
for (int j = 0; j <= Oxy; j++)
{
for (int k = 0; k <= Nit; k++)
{
DPTable [i][j][k] = DPTable [i-1][j][k];
if (DPTable [i-1][max(0, j-OxyArr[i-1])][max(0, k-NitArr[i-1])] != -1)
{
if (DPTable [i][j][k] < DPTable [i-1][max(0, j-OxyArr[i-1])][max(0, k-NitArr[i-1])] + WeightArr[i-1])
DPTable [i][j][k] = DPTable [i-1][max(0, j-OxyArr[i-1])][max(0, k-NitArr[i-1])] + WeightArr[i-1];
if (j >= Oxy && k >= Nit && Solution > DPTable [i][j][k]) Solution = DPTable [i][j][k];
}
}
}
}
printf ("%d\n", Solution);
}
}
Try this, 1 2 2 2 1 1 1 2 2 50
The answer should be 50. You are not getting this...I hope this will help you.
Try finding out dp[i][j][k] where dp[i][j][k] denotes minimum cylinders required from first k cylinders such that i litre of Oxygen and j Litre of Nitrogen is satisfied. dp[i][j][k]=min(dp[i][j][k-1],dp[max(0,i-array[k][0])][max(0,j-array[k][1])][k-1]+array[k][2]),where array[k] stores the cylinder parameters as stated in problem statement clearly.
Take i litre oxygen and j litre nitrogen from k-1 cylinders or take the kth cylinder..
Base Case: dp[i][j][0]=INF for all i<=Oxygen and j<=Nitrogen dp[0][0][i]=0 fro all i<=Number of Cylinders.
Hope this Helps.