http://lx.lanqiao.cn/problem.page?gpid=T120
问题描述
X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。 地宫的入口在左上角，出口在右下角。 小明被带到地宫的入口，国王要求他只能向右或向下行走。 走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。 当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。 请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。
输入格式
输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12) 接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值
输出格式
要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。
样例输入
2 2 2 1 2 2 1
样例输出
2
样例输入
2 3 2 1 2 3 2 1 5
样例输出
14
dp(i,j,k,l) ：代表走到(i,j)，最大值为k,已选取个数为l的最大方案数
注意两点：
1.dp在加的时候要mod
2.输入a[i][j]的时候，要加一，与0不取区分开（因为价值有0的情况）
自己更新别人
// 去吧！皮卡丘! 把AC带回来！// へ ／|// /＼7 ∠＿/// / │ ／ ／// │ Z ＿,＜ ／ /`ヽ// │ ヽ / 〉// Y ` / /// ｲ● ､ ● ⊂⊃〈 /// () へ | ＼〈// >ｰ ､_ ィ │ ／／// / へ / ﾉ＜| ＼＼// ヽ_ﾉ (_／ │／／// 7 |／// ＞―r￣￣`ｰ―＿//**************************************#pragma comment(linker, "/STACK:1024000000,1024000000")#includeusing namespace std;typedef long long ll;#define inf 2147483647const ll INF = 0x3f3f3f3f3f3f3f3fll;#define ri register inttemplate inline T min(T a, T b, T c) { return min(min(a, b), c); }template inline T max(T a, T b, T c) { return max(max(a, b), c); }template inline T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d));}template inline T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d));}#define scanf1(x) scanf("%d", &x)#define scanf2(x, y) scanf("%d%d", &x, &y)#define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z)#define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X)#define pi acos(-1)#define me(x, y) memset(x, y, sizeof(x));#define For(i, a, b) for (int i = a; i <= b; i++)#define FFor(i, a, b) for (int i = a; i >= b; i--)#define bug printf("***********\n");#define mp make_pair#define pb push_backconst int maxn = 2e5 + 10;// name*******************************int n, m, K;int a[55][55];int dp[55][55][14][14];int ans = 0;int mod = 1000000007;// function******************************//***************************************int main() { // ios::sync_with_stdio(0); cin.tie(0); // freopen("test.txt", "r", stdin); // freopen("outout.txt","w",stdout); cin >> n >> m >> K; For(i, 1, n) { For(j, 1, m) { cin >> a[i][j]; a[i][j]++; } } memset(dp, 0, sizeof(dp)); dp[1][1][a[1][1]][1] = 1; dp[1][1][0][0] = 1; For(i, 1, n) { For(j, 1, m) { For(k, 0, 13) { For(l, 0, K) { if (dp[i][j][k][l] == 0) continue; if (k < a[i + 1][j]) { dp[i + 1][j][a[i + 1][j]][l + 1] += dp[i][j][k][l]; dp[i + 1][j][a[i + 1][j]][l + 1] %= mod; } if (k < a[i][j + 1]) { dp[i][j + 1][a[i][j + 1]][l + 1] += dp[i][j][k][l]; dp[i][j + 1][a[i][j + 1]][l + 1] %= mod; } dp[i + 1][j][k][l] += dp[i][j][k][l]; dp[i + 1][j][k][l] %= mod; dp[i][j + 1][k][l] += dp[i][j][k][l]; dp[i][j + 1][k][l] %= mod; // cout << dp[i][j][k][l] << " "; } } } // cout << endl; } For(i, 0, 13) { ans += dp[n][m][i][K]; ans %= mod; } cout << ans; return 0;}
别人更新自己
// 去吧！皮卡丘! 把AC带回来！// へ ／|// /＼7 ∠＿/// / │ ／ ／// │ Z ＿,＜ ／ /`ヽ// │ ヽ / 〉// Y ` / /// ｲ● ､ ● ⊂⊃〈 /// () へ | ＼〈// >ｰ ､_ ィ │ ／／// / へ / ﾉ＜| ＼＼// ヽ_ﾉ (_／ │／／// 7 |／// ＞―r￣￣`ｰ―＿//**************************************#pragma comment(linker, "/STACK:1024000000,1024000000")#includeusing namespace std;typedef long long ll;#define inf 2147483647const ll INF = 0x3f3f3f3f3f3f3f3fll;#define ri register inttemplate inline T min(T a, T b, T c) { return min(min(a, b), c); }template inline T max(T a, T b, T c) { return max(max(a, b), c); }template inline T min(T a, T b, T c, T d) { return min(min(a, b), min(c, d));}template inline T max(T a, T b, T c, T d) { return max(max(a, b), max(c, d));}#define scanf1(x) scanf("%d", &x)#define scanf2(x, y) scanf("%d%d", &x, &y)#define scanf3(x, y, z) scanf("%d%d%d", &x, &y, &z)#define scanf4(x, y, z, X) scanf("%d%d%d%d", &x, &y, &z, &X)#define pi acos(-1)#define me(x, y) memset(x, y, sizeof(x));#define For(i, a, b) for (int i = a; i <= b; i++)#define FFor(i, a, b) for (int i = a; i >= b; i--)#define bug printf("***********\n");#define mp make_pair#define pb push_backconst int maxn = 2e5 + 10;// name*******************************int n, m, K;int a[55][55];int dp[55][55][15][15];int ans = 0;int mod = 1000000007;// function******************************//***************************************int main() { // ios::sync_with_stdio(0); cin.tie(0); // freopen("test.txt", "r", stdin); // freopen("outout.txt","w",stdout); cin >> n >> m >> K; For(i, 1, n) { For(j, 1, m) { cin >> a[i][j]; a[i][j]++; } } memset(dp, 0, sizeof(dp)); dp[1][1][a[1][1]][1] = 1; dp[1][1][0][0] = 1; For(i, 1, n) { For(j, 1, m) { if (i == 1 && j == 1) continue; For(k, 0, 13) { For(l, 0, K) { if (a[i][j] > k) { dp[i][j][a[i][j]][l + 1] += dp[i - 1][j][k][l]; dp[i][j][a[i][j]][l + 1] %= mod; dp[i][j][a[i][j]][l + 1] += dp[i][j - 1][k][l]; dp[i][j][a[i][j]][l + 1] %= mod; } dp[i][j][k][l] += dp[i][j - 1][k][l]; dp[i][j][k][l] %= mod; dp[i][j][k][l] += dp[i - 1][j][k][l]; dp[i][j][k][l] %= mod; } } } } For(i, 0, 12) { ans += dp[n][m][i][K]; ans %= mod; } cout << ans; return 0;}