AcWing 1212. 地宫取宝
原题链接
中等
作者:
ofs
,
2024-04-11 23:35:36
,
所有人可见
,
阅读 2
//0-1背包问题与最长字串序列的结合
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define end "\n"
#define int long long
using namespace std;
const int N=55,MOD=1000000007;
int n,m,k;
int w[N][N]; //每个位置的原始值
int f[N][N][13][14]; //第三个下标表示 取了几件,范围0-12
//第四个下标表示取的值,-1-12,下标不能为负数,所以设定为0-13,共14个
//则在存储价值的时候,需要对价值进行加1操作
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>k;
for(int i=1;i<=n;i++) //注意m与n都从1开始
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; //在起点,但是不选择当前物品,注意此时价值是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];//使用引用,后续方便使用
//刚开始对应的方案数都是0,所以第一条相加不会影响值
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]) //注意此处约束条件,u-1下标不能为负数,所以u一定要大于0
{
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;
//题目要求的是所有能够从起点走到终点且最后刚好带出K件宝物的方案数目
//其中n m(终点坐标) k(带出宝物的数量)的值是固定的,只有最后取得的宝物的最大价值不是固定的
//所以需要循环所有可能的最大价值,把对应的方案数加到一起
//!!注意取模运算 所有数相加后取模等于取模后相加再取模
for(int i=0;i<=13;i++) res=(res+f[n][m][k][i])%MOD;
cout<<res<<endl;
return 0;
}