一道值得思考的动规题,有很多细节都需要注意。
#include <bits/stdc++.h>
#define ll long long
#define MAXN 51
#define MAXK 13
#define MOD 1000000007
#define f(a,b,c) for(int a=b;a<=c;++a)
using namespace std;
int n,m,k;
int G[MAXN][MAXN];
/*
骗分暴力
int ans;
void dfs(int x,int y,int num,int max) {
if(num > k || x > n || y > m)
return;
if(x == n && y == m) {
if(num == k)
ans = (ans + 1) % MOD;
if(num == k - 1 && G[x][y] > max)
ans = (ans + 1) % MOD;
}
if(G[x][y] > max) {
dfs(x+1,y,num+1,G[x][y]);
dfs(x,y+1,num+1,G[x][y]);
}
dfs(x+1,y,num,max);
dfs(x,y+1,num,max);
}
int main() {
ios::sync_with_stdio(false);
cin>>n>>m>>k;
f(i,1,n)
f(j,1,m)
cin>>G[i][j];
dfs(1,1,1,G[1][1]);
cout<<ans;
return 0;
}
*/
int maxv;
ll ans;
int dp[MAXN][MAXN][MAXK][MAXK];
// i行j列取c个宝物最大价值为v
int main() {
ios::sync_with_stdio(false);
cin>>n>>m>>k;
f(i,1,n)
f(j,1,m) {
cin>>G[i][j];
++G[i][j];
//处理价值为0的宝物
maxv = max(maxv,G[i][j]);
//记录最大价值
}
dp[1][1][0][0] = dp[1][1][1][G[1][1]] = 1;
//初始化,第一件物品拿与不拿
f(i,1,n)
f(j,1,m)
f(c,0,k)
f(v,0,maxv) {
if(i <= n - 1) {
if(G[i+1][j] > v)
dp[i+1][j][c+1][G[i+1][j]] = (dp[i+1][j][c+1][G[i+1][j]] + dp[i][j][c][v]) % MOD;
//拿
dp[i+1][j][c][v] = (dp[i+1][j][c][v] + dp[i][j][c][v]) % MOD;
//不拿
}
if(j <= m - 1) {
if(G[i][j+1] > v)
dp[i][j+1][c+1][G[i][j+1]] = (dp[i][j+1][c+1][G[i][j+1]] + dp[i][j][c][v]) % MOD;
dp[i][j+1][c][v] = (dp[i][j+1][c][v] + dp[i][j][c][v]) % MOD;
}
}
f(i,0,maxv)
ans = (ans + dp[n][m][k][i]) % MOD;
//把每种最高价值相加
cout<<ans;
return 0;
}