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.

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