Solution:
First of all, we do not consider the condition that the number of good numbers is exactly equal to k, we first consider the characteristics of the good number itself.
It is not difficult to find that n must be in the maxima anyway.
In this way, it is natural that if m=1, then this x is and can only be n.
Furthermore, when m=1, there is a solution if and only if k=1, and the solution is n!. Otherwise, there must be no solution.
Now let us consider the case of m=2. It is not difficult to think that n-1 must be a good number, but can other numbers become good numbers?
For example, if n-5 is a good number, we can give the following structure [?,...,?, n-5, ?,...,?, n, n-1, n-2,n -3,n-4]. At this time, n-5 is also a good number.
But after carefully considering the reasons why n-5 can be a good number, we found that in fact, all the values on the right side of n have nothing to do with n-5.
So we can get two important conclusions:
- Within a certain interval, with the maximum value in the interval as the boundary, the values on the left side of the maximum value and the right side of the maximum value will not affect each other.
- In a certain interval, the maximum value of this interval must appear in the maxima value.
With these two conclusions, we can roughly think of dividing the sub-problems by the maximum value of the interval. We directly define dp[m][n][k] according to the meaning of the question, and try to get the state transition equation according to the interval maximum value.
Due to conclusion 2, it is not difficult to think that dp[m][n][k] must only be related to dp[m-1][?][?].
Due to conclusion 1, we can further discover that $$dp[m][n][k]=\sum_{left_n=0}^{n-1}\sum_{k'=0}^k C_n^{left _n}\cdot dp[m-1][left_n][k']\cdot dp[m-1][(n-1)-left_n][k-k']$$It means that for n numbers, after removing the maximum value, I choose left_n numbers from the remaining n-1 numbers to the left side, and let there be exactly k' good numbers on the left side. In this way, there are (n-1)-left_n numbers left in the right part, and there must be exactly k-k' good numbers.
Finally, combine the conclusion at the beginning when m=1, we solved this problem.
Code:
Java
C++
