AcWing 1212. 地宫取宝
原题链接
中等
作者:
我是java同学
,
2023-01-11 15:03:58
,
所有人可见
,
阅读 126
dp
- 选择维度可以看数据范围的提示
- 选择维度还可以看限制
- 维度:
i
,j
坐标,k
宝贝的件数,c
宝贝的价值
- 时间复杂度:50 * 50 * 12 * 13
- 集合:所有从起点走到(i, j),且
已经取了
k件物品,且最后一件
物品的价值是c的合法方案集合(都是最后一步)
- 初始化
- 取第一个位置
f(1,1,1,w[1][1])
- 不取第一个位置
f(1,1,0,-1)
- 为什么要是-1?保证格子中的宝贝价值比小明手中任意宝贝价值都大,以便后来走的过程中能够取任何物品
- 如果是0意味着下一个数不能取0
- 因为一般数组不用负数,所以把所有价值都加
1
,-1
用0
表示
- 问题
- 写最后一维是
c
的那部分状态方程怎么写——多加一层循环
- 最后输出结果价值那一维
c
怎么写——循环枚举,因为不知道最后手里的价值是多少,把所有可能加起来
#include <iostream>
using namespace std;
const int N = 55, mod = 1000000007;
int n, m, k;
int f[N][N][13][14];
int w[N][N];
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] ++ ;
}
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;
}
}
}
}
int res = 0;
for (int i = 0; i <= 13; i ++ ) res = (res + f[n][m][k][i]) % mod;
cout << res << endl;
return 0;
}