Блог пользователя afruizc

Автор afruizc, 11 лет назад, По-английски

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.

Теги dp
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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