AcWing 1212. Underground palace treasure taking

King X has an underground palace treasure house, which is n × A matrix of m squares, with one baby in each lattice, and each baby is attached with a value tag.

The entrance of the underground palace is in the upper left corner and the exit is in the lower right corner.

Xiao Ming was taken to the entrance of the underground palace. The king asked him to walk only to the right or down.

When walking through a grid, if the value of the baby in that grid is greater than that of any baby in Xiaoming's hand, Xiaoming can pick it up (of course, he can also not take it).

When Xiaoming comes to the exit, if the baby in his hand happens to be k pieces, these babies can be given to Xiaoming.

Please help Xiao Ming calculate how many different action plans he can get this k treasure in a given situation.

Input format
The first line contains three integers, N, m and K. see the title description for the meaning.

Next n lines, each line has m integers Ci to describe the treasure value of each grid of the treasure matrix.

Output format
Output an integer indicating the number of action plans for exactly k babies.

This number may be very large. Output the result of its modulus of 100000007.

Data range
1≤n,m≤50,
1≤k≤12,
0≤Ci≤12
Input example 1:

2 2 2
1 2
2 1

Output example 1:

2

Input example 2:

2 3 2
1 2 3
2 1 5

Output example 2:

14

At the beginning of this problem, I thought of using three-dimensional dp storage d p [ k ] [ i ] [ j ] dp[k][i][j] dp[k][i][j]
i. j means running to the point of {i,j}, and K means there are k items in the backpack. I really didn't do it, so I looked at it yxc video Then I learned a four-dimensional approach. It seems that thinking should be bold. Everything can be dp
Take a look at y the general idea.

Problem solving ideas:

This problem can be solved in four dimensions DP Solution due to contact DP Before long, it was really a challenge for me, but after most of the day's struggle, it was the idea of this problem
 It's sorted out. I imitate it here yxc of DP Analytical thinking: consider with the idea of set DP
 The first thing to be clear is that to get the items in the current grid, this item must be larger than the items currently owned, so it has a property: the items taken later
 Larger than the item in front
 Then draw the following analysis diagram:

The difficulty lies in the state calculation part, which is associated with the 01 knapsack problem. For each item, there are two choices: take it or not. It is certain that you can not take it. If you want to take it, take it
 Meet the condition that the backpack can be put down
 The same is true here. For each item, you can not select it, that is, you can directly transfer the status from the previous step, but if you want to obtain(i,j)(i,j)Location items,
Must meet the current kk and a[i][j]a[i][j]Equal, because it has been analyzed above, if we take it now a[i][j]a[i][j]，Then it must be what it is now
 There are the largest items, which corresponds to our definition of four-dimensional array at the beginning
 In the specific state transition, if it is not selected, the state will be completely transferred from the previous step cntcnt and kk Transfer over; If you choose, you should choose the last step
cnt−1cnt−1 The maximum value of all items can only be 1 step k−11...k−1，When the number of schemes in these States is accumulated, it can become a choice
 Conditions of pre-sale goods
 matters needing attention:

Because the value range of all items in this question is 0... 120... 12, you can increase them all, and the range becomes 1... 131... 13, because we record the scheme
 It only cares about the size relationship between various items. The specific value does not affect the answer, but 00 can be treated as a special boundary
 If you don't understand the whole process, you can simulate it with paper and pen to see what the value of each state should be

Author: Daniel Control y
 Link: https://www.acwing.com/solution/content/7116/
Source: AcWing
 The copyright belongs to the author. For commercial reprint, please contact the author for authorization. For non-commercial reprint, please indicate the source.

The boss's idea is very clear. According to the boss's idea, I wrote the corresponding code.
The code is as follows

#include<iostream>
#include<algorithm>

using namespace std;

const int N=55,M=15,MOD=1000000007;

int dp[N][N][13][14];//When opening the array, be careful to turn it up
int wi[N][N];

int main(void)
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    cin>>wi[i][j],wi[i][j]++;//Pay attention to adding 1, because if the value is 0, it also means that it is selected
    dp[1][1][1][wi[1][1]]=1;
    dp[1][1][0][0]=1;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     {
         if(i==1&&j==1) continue;//It's already lined up
         else
         {
             for(int a=0;a<=k;a++)
              for(int b=0;b<=13;b++)
              {
                  int &val=dp[i][j][a][b];//Similar to teacher Yang's camera sequence, introduce the complexity of the code
                  val=(val+dp[i-1][j][a][b])%MOD;//Unselected
                  val=(val+dp[i][j-1][a][b])%MOD;//Unselected
                  if(b==wi[i][j]&&a)//Only when the backpack has something and the current value is the coordinate value.
                  {
                          for(int p=0;p<b;p++)
                          {
                              val=(val+dp[i-1][j][a-1][p])%MOD;
                              val=(val+dp[i][j-1][a-1][p])%MOD;
                          }
                  }
              }
         }
     }
    int res=0;
    for(int i=1;i<=13;i++)  res=(res+dp[n][m][k][i])%MOD;
    //The total code of y starts from 1, which means that it has never been selected. I start from 1 instead
    cout<<res;
}