AcWing 1212. 地宫取宝
原题链接
中等
作者:
Bear_King
,
2021-01-13 09:34:41
,
所有人可见
,
阅读 459
地宫取宝:多维线性DP
摘花生模型+最长上升子序列模型 的扩展变型题
下面这种方法的时间复杂度:O(n^5)
#include<iostream>
using namespace std;
//
const int N = 55 , MOD = 1e9+7;
/*
1≤n,m≤50,
1≤k≤12,
0≤Ci≤12
*/
int f[N][N][13][14];//所有从起点走到(i,j),且拿了k件物品及最后一间物品的最大价值为C
int w[N][N];//每个格子上的原始价值
int n,m,k;
int main()
{
scanf("%d %d %d",&n,&m,&k);
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
scanf("%d",&w[i][j]);
w[i][j] ++;//防止数组越界
}
//初始化
f[1][1][1][w[1][1]] = 1;
f[1][1][0][0] = 1;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
{
//去掉第一格的枚举
if(i == 1 && j == 1) continue;
for(int u = 0;u <= k;u ++)
for(int v = 0;v <= 13;v ++)
{
int &val = f[i][j][u][v];
//不取:
val = (val + f[i-1][j][u][v]) % MOD;
val = (val + f[i][j-1][u][v]) % MOD;
//取(加限制):
if(u > 0 && v == w[i][j])
{
for(int c = 0;c < v;c ++)
{
val = (val + f[i-1][j][u-1][c]) % MOD;
val = (val + f[i][j-1][u-1][c]) % MOD;
}
}
}
}
//把出口位置在k件物品的限制下的所有方案累加得总方案数
int res = 0;
for(int i = 0;i <= 13;i ++) res = (res + f[n][m][k][i]) % MOD;
cout<<res<<endl;
return 0;
}
有更好的方法了,欢迎评论分享