afruizc's blog

By afruizc, 9 years ago, In English

Hello guys, this is my first post, and yes, it is asking for some help.

I am trying to solve this problem using dp. I know there is a greedy solution, but I would really like to solve it using dp. The thing is that the solution I devised uses 1000*1000*1000 in space.

Does anyone know a better way to solve it using dp.

Thanks for your help.

Tags dp
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think we can define dp1[i][j] as the maximum profit if we put kth~(j-1)th people into ith plane, where (j-k)<=a[i], k>=1 (if k==j,then we don't put any people into ith plane) dp2[i][j] can be defined as the minimum profit as the max profit

dp1[1][j] = a[i]+(a[i]-1)+...+(a[i]-j+2) for 1<=j<=a[i]+1 dp1[i][j] = max(dp1[i-1,j],dp1[i-1][j-k]+(a[i]+...+(a[i]-k+1)) for 1<=k<=a[i] and 1<=j<=m+1

finally obtain dp1[n][m+1] and output it. Not completely sure about this solution but it may work with O(nm^2) time and O(nm) space complexity. Surely annoying implementation.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your reply. I will try to implement this solution and see if it works :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why dont you make two arrays namely MI[m],MA[m] which stores the same values a[i ......m], Now iterate from 1 to n times through MI[] and MA[] simultaneously to find minimum and maximum values respectively from MI[] and MA[] , thereafter decreasing the value obtained, by 1 in the corresponding arrays.3852749. Thus you can add the minimum and maximum values to find the solution

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your solution works, but I am looking for a DP solution. I solved the problem using heaps and it runs in O(nlogm), it's just that I want to get some practice solving problems like these using dp. Thanks for the reply

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the post is tagged dp , I felt this to be a right place to ask my query ... Many of the coders on codeforces are outstanding in dynamic programming but I am still a beginner in it . I know what dynamic programming is and how it works in different contexts , but I find it hard to implement it into problems . Can someone please suggest me some ways to overcome this difficulty . Any sugggestions would be welcomed !!!

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The key to be good at DP is to practice and try to solve as many problems as possible. After a while you would get the sense of it, and it will be "reduced" to -> Finding the state, finding the transition between states. There are reaaaaaally good resources where you can grasp some of the basics of DP, here in cf, in tc, or you can just look it up on your favorite search engine. You can start trying the traditional problems: Knapsack, LIS, TSP, coin change, matrix chain, cutting rod, etc... After you master this, you can start by solving some of the non-traditional problems here in cf, or even in tc and uva.

    I hope this helps.