acwing1212地宫取宝:好题好题,结合经典的俩dP模型
作者:
总打瞌睡的天天啊
,
2024-10-25 13:34:45
,
所有人可见
,
阅读 4
#include<iostream>
#include<algorithm>
using namespace std;
const int N=55,MOD=1000000007;
int w[N][N];
int f[N][N][14][14];
int n,m,scheme;
int main()
{
cin>>n>>m>>scheme;
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= m ; j++){
cin>>w[i][j];
w[i][j]++;
}
}
//(1,1)位置不拿,方案数是0
f[1][1][0][0] = 1;
//(1,1)位置拿,方案数1,最后一个数是w[1][1]
f[1][1][1][w[1][1]] = 1;
//遍历所有位置
for(int i = 1 ; i <= n ; i ++){
for(int j = 1 ; j <= m ; j++){
//遍历所有已经拿的数量
for(int k = 0 ; k <= scheme ; k ++){
//遍历已经拿了的物品的最大值
for(int c = 0 ; c <= 13 ; c++){
int &v = f[i][j][k][c];
//从左来,不拿
v = (v + f[i-1][j][k][c]) % MOD;
//从上来,不拿
v = (v + f[i][j-1][k][c]) % MOD;
//变成最长上升子序列问题。遍历从0到c的所有的价值
//注意:拿了物品(k>0)的情况下才有下面这段代码的必要
if(k > 0 && w[i][j] == c){
for(int p = 0 ; p < c ; p ++){
v = (v + f[i-1][j][k-1][p]) % MOD;
v = (v + f[i][j-1][k-1][p]) % MOD;
}
}
}
}
}
}
int res = 0;
//同最小上升子序列,要遍历所有可能的价值,才能得到最大值
for(int i = 1 ; i<=13 ; i++) res = (res + f[n][m][scheme][i]) % MOD;
cout << res << endl;
return 0;
}