[ブルーブリッジカップ]地宮取宝

X王には地宮の宝庫があります.nです.×m個の格子の行列、各格子に1枚の宝物を置いて、各宝物は価値のラベルを貼っています.
地宮の入り口は左上にあり、出口は右下にあります.
明ちゃんは地宮の入り口に連れて行かれ、王は右か下にしか歩けないと要求した.
ある格子を通るとき、その格子の中の宝物の価値が明ちゃんの手の中の任意の宝物の価値よりも大きい場合、明ちゃんはそれを手に取ることができます(もちろん、取らなくてもいいです).
明ちゃんが出口に着いたとき、彼の手の中の宝物がちょうどk枚だったら、これらの宝物は明ちゃんにあげることができます.
明ちゃんの計算を手伝ってください.与えられた局面の下で、彼は何種類の異なる行動案がこのkつの宝物を得ることができますか.
フォーマットの最初の行の3つの整数を入力して、n,m,k、意味はテーマの説明を参照してください.
次にn行、各行にm個の整数Ciがあり、宝庫行列の各格子の宝物価値を記述する.
出力フォーマットは整数を出力し、ちょうどk個の宝物を取る行動案数を表す.
この数字は大きく、1000000007の型取りの結果を出力する可能性があります.
データ範囲1≦n,m≦50,1≦k≦12,0≦Ci≦12入力サンプル1:2 2 2 1 2 2 2 1出力サンプル1:2入力サンプル2:2 3 2 1 2 3 2 2 3 1 5出力サンプル2:14
解題構想:まずdp[i][j][cnt][k]を定義すると、明ちゃんが左上から(i,j)cnt個の物品を持っていて、手の最大価値がkである歩き方を意味し、この問題の中で価値の範囲は(0,12)であり、地図の各点の物品が0である可能性があることを意味するので、データを読み込むときに、各データを+1し、このように価値の範囲は(1,13)になり、初期化の問題を考えるのに便利になります.それから、関係式を考えてみましょう.この点で取るか取らないか、コードは次のようになります.

dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % MOD;
dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % MOD;

ここでは別々に書きます.そして結果は%MODになります.そうしないとデータが爆発します.そして、明ちゃんが取るたびに取るものが前のものよりも大きくなります.そして、この点のものが取れると、必ず一致します.この点のものの価値は私たちのdp[i][j][cnt][k]のk値に等しくなります.そして、品物を取ると、cntは必ず0より大きくなります.そして、どのように初期化するかを考えて、起点で、明ちゃんはこのアイテムを取る可能性もあるし、取らない可能性もあるので、取らないのがdp[1][1][0][0]=1で、このアイテムdpを取る[1][1][1][w[1][1]]
コードは次のとおりです.

#include 
using namespace std;
const int N = 55;
const int MOD = 1000000007;
int dp[N][N][15][15];
int w[N][N];
int n, m, k;

int main() {
     
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
     
			cin >> w[i][j];
			w[i][j]++;
		}

	dp[1][1][0][0] = 1;
	dp[1][1][1][w[1][1]] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int cnt = 0; cnt <= k; cnt++)
				for (int v = 0; v <= 13; v++) {
     
					dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt][v]) % MOD;
					dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt][v]) % MOD;

					if (cnt > 0 && w[i][j] == v) {
     
						for (int s = 0; s < v; s++) {
     
							dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i - 1][j][cnt - 1][s]) % MOD;
							dp[i][j][cnt][v] = (dp[i][j][cnt][v] + dp[i][j - 1][cnt - 1][s]) % MOD;

						}
					}
				}

	int res = 0;
	for (int i = 0; i <= 13; i++) {
     
		res = (res + dp[n][m][k][i]) % MOD;
	}

	cout << res << endl;
	return 0;

}