afruizc's blog

By afruizc, 10 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

| Write comment?
10 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.

10 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 !!!