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

Автор TwinHter, история, 3 года назад, По-английски

Hi everyone. I'm having trouble thinking about a dp problem. The problem is:t There are n students with height from 1->n and one number k(n<=2000, k<=n) You have to line up ALL students so that one person in front of the first person and can see exactly k faces. Example: 2 5 1 6 3 4 => that person can see the face of 1st, 2nd and 4th student. Your work is count how many ways to line up ALL n students. (module 1e9+7)

Test Inp: 3 2 => Output 3 (2 1 3, 1 3 2, 2 3 1)

Thanks for your help.

//Ps Sorry, I am not good at English :((

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

Auto comment: topic has been updated by TwinHter (previous revision, new revision, compare).

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Hint : use dp[i][j] is number of ways to sort i student and we can see j student from head. dp[i][j]=dp[i-1][j]*(i-1)+dp[i-1][j-1].After use combination to calculate the answer. ps: i need you help me to be a master.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    I can understand dp[i-1][j-1] but i cant understand dp[i-1][j]*(i-1). Can you explain that?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      What I understand we are going in descending order, initially we've i-1 students, so there are i total places for ith student:

      Case 1: If we place him behind anyone(i-1 choices) we will not see him and so number of students visible remains the same. We get (i-1)*(dp[i-1][j]) term.

      Case 2: If we place him infront the number of students visible increase by 1 so we get dp[i-1][j-1] term.

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

        oh I understanded. I thought the i_th student is the tallest.

        Thanks a lot.