Help please : Doubt in DP

codeforces
dynamic-programming

#1

I was trying solving the problem George and job of contest 467C. And my solution is : http://ideone.com/2cC2Fb I am using dp and finding out dp[k]* i.e. the maximum sum of k subsets of the size m from 1 to i in the given array input. Thus, that sum is computed as :

dp[k][j]= max(dp[k-1][j-size]+sum[j],dp[k][j-1]);

I.e for a given K, i’ll get the maximum of the addition of sum (k-1) subset which ends at j-size, size here is m +sum[j] which is basically the subset [j-size,j]. Either I am including this or I am not including thi, the deciding factor is the maximum sum. I am getting WA on 22nd test case. I thought it’s exceeding the range, and so made it unsigned long long int also, but then it gives Memory limit exceeded. I went across one of the solution, I only saw the memory used by the arrays and it was the same as of my code. Then, why such error?


#2

if(m==1)

{

for(i=0;i<n;i++)

cin>>a*;

if(ki==1){

cout<<a[n-1]<<endl;

return 0;

}



Why did u do this?? :stuck_out_tongue:

If n=1 and k=1 then will the answer be the last number??
Consider the following test case:

3 1 1
3 2 1

Clearly the answer is 3. But your code gives 1!
I dint look further into the code after seeing this error! 

Dont forget up upvote and accept! ;)

#3
Line number 30. Why have u done a[0]=0??
A test case for which your code fails-

3 1 3
3 2 1

Hopefully this brings an AC! :)

#4

must have forgotten to sort the array inside the loop (note that sorting is done after this ) :wink:


#5

Yeah, corrected that. Just had to place sort before. But its still the same . WA on case 22.


#6

note: You can view the test case on which your code is giving WA on codeforces…


#7

Oh, no reason! Thanks, that gave me an AC.