X 国王有一个地宫宝库,是 n × m n×m n × m 个格子的矩阵,每个格子放一件宝贝,每个宝贝贴着价值标签。
地宫的入口在左上角,出口在右下角。
小明被带到地宫的入口,国王要求他只能向右或向下行走。
走过某个格子时,如果那个格子中的宝贝价值比小明手中任意宝贝价值都大,小明就可以拿起它(当然,也可以不拿)。
当小明走到出口时,如果他手中的宝贝恰好是 k k k 件,则这些宝贝就可以送给小明。
请你帮小明算一算,在给定的局面下,他有多少种不同的行动方案能获得这 k k k 件宝贝。
输入格式
第一行 3 3 3 个整数,n , m , k n,m,k n , m , k ,含义见题目描述。
接下来 n n n 行,每行有 m m m 个整数 C i C_i C i 用来描述宝库矩阵每个格子的宝贝价值。
输出格式
输出一个整数,表示正好取 k k k 个宝贝的行动方案数。
该数字可能很大,输出它对 1000000007 1000000007 1000000007 取模的结果。
数据范围
1 ≤ n , m ≤ 50 1≤n,m≤50 1 ≤ n , m ≤ 50 ,
1 ≤ k ≤ 12 1≤k≤12 1 ≤ k ≤ 12 ,
0 ≤ C i ≤ 12 0≤C_i≤12 0 ≤ C i ≤ 12 .
输入样例1:
输出样例1:
输入样例2:
输出样例2:
思路
题目要求在格子上只能向下和向右走,很明显是要用DP解题,重点是如何设置状态。
当前所处的位置 ( i , j ) (i,j) ( i , j ) ,必然是需要记录的状态;为考察最后走到 ( n , m ) (n,m) ( n , m ) 后拿到 k k k 个物品的方案数,当前拿到的物品数 c c c 也是状态之一;取的物品的价值(我们用 v a l ( i , j ) val(i,j) v a l ( i , j ) 表示位置 ( i , j ) (i,j) ( i , j ) 物品的价值)需要严格递增,因此我们需要记录已经取的物品的最大价值。设 f ( i , j , c , v ) f(i,j,c,v) f ( i , j , c , v ) 表示走到位置 ( i , j ) (i,j) ( i , j ) ,取了 c c c 个物品且最大价值为 v v v 的方案数。
考虑取或不取 ( i , j ) (i,j) ( i , j ) 的物品:若取,则取完后最大物品的价值必须为 v a l ( i , j ) val(i,j) v a l ( i , j ) ,前面 c − 1 c-1 c − 1 个物品的最大价值在 [ 0 , v a l ( i , j ) ) [0,val(i,j)) [ 0 , v a l ( i , j )) 的整数区间内(若 v a l ( i , j ) = 0 val(i,j)=0 v a l ( i , j ) = 0 需要特判),f ( i , j , c , v a l ( i , j ) ) = ∑ v = 0 v a l ( i , j ) − 1 [ f ( i − 1 , j , c − 1 , v ) + f ( i , j − 1 , c − 1 , v ) ] f(i,j,c,val(i,j))=\sum\limits_{v=0}^{val(i,j)-1}[f(i-1,j,c-1,v)+f(i,j-1,c-1,v)] f ( i , j , c , v a l ( i , j )) = v = 0 ∑ v a l ( i , j ) − 1 [ f ( i − 1 , j , c − 1 , v ) + f ( i , j − 1 , c − 1 , v )] ;若不取,则 f ( i , j , c , v ) = f ( i − 1 , j , c , v ) + f ( i , j − 1 , c , v ) f(i,j,c,v)=f(i-1,j,c,v)+f(i,j-1,c,v) f ( i , j , c , v ) = f ( i − 1 , j , c , v ) + f ( i , j − 1 , c , v ) 。
现在考虑边界条件,若一直什么都不取,则 f ( i , j , 0 , 0 ) = ( i + j − 2 i − 1 ) f(i,j,0,0)=\binom{i+j-2}{i-1} f ( i , j , 0 , 0 ) = ( i − 1 i + j − 2 ) ,即从 ( 1 , 1 ) (1,1) ( 1 , 1 ) 走到 ( i , j ) (i,j) ( i , j ) 的方案数;若 v a l ( i , j ) = 0 val(i,j)=0 v a l ( i , j ) = 0 ,有特判 f ( i , j , 1 , 0 ) = ( i + j − 2 i − 1 ) f(i,j,1,0)=\binom{i+j-2}{i-1} f ( i , j , 1 , 0 ) = ( i − 1 i + j − 2 ) 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 #include <iostream> using namespace std;typedef long long ll;const int MOD = 1000000007 ;ll f[51 ][51 ][202 ][15 ]; ll val[101 ][101 ]; int k, n, m;ll C[101 ][101 ]; void initC () { C[0 ][0 ] = 1 ; for (int i = 1 ; i <= 100 ; i++) { C[i][0 ] = 1 ; for (int j = 1 ; j <= 100 ; j++) { C[i][j] = (C[i - 1 ][j] + C[i - 1 ][j - 1 ]) % MOD; } } } int main () { initC (); cin >> n >> m >> k; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { cin >> val[i][j]; } } f[1 ][1 ][1 ][val[1 ][1 ]] = 1 ; for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= m; j++) { f[i][j][0 ][0 ] = C[i + j - 2 ][i - 1 ]; if (i == j && j == 1 ) { continue ; } if (val[i][j] == 0 ) { f[i][j][1 ][0 ] = C[i + j - 2 ][i - 1 ]; } for (int c = 1 ; c <= i + j - 1 ; c++) { for (int v = 0 ; v <= 12 ; v++) { if (val[i][j] > v) { f[i][j][c][val[i][j]] += (f[i - 1 ][j][c - 1 ][v] + f[i][j - 1 ][c - 1 ][v]) % MOD; f[i][j][c][val[i][j]] %= MOD; } f[i][j][c][v] += (f[i - 1 ][j][c][v] + f[i][j - 1 ][c][v]) % MOD; } } } } ll ans = 0 ; for (int v = 0 ; v <= 12 ; v++) { ans += f[n][m][k][v]; ans %= MOD; } cout << ans << endl; return 0 ; }