1212. 地宫取宝

1212. 地宫取宝 1212. 地宫取宝 四维dp

是最长上升子序列和摘花生两个题的结合版。

二维地图，类似摘花生只有当当前位置的宝物价值严格大于当前背包中任一物品价值时才可拿起。类似最长上升子序列此题数据范围较小，只有50*50 = 2500种情况，这意味着dp的维度可能比较多。

---

样例解读

2 3 2
1 2 3
2 1 5
res = 14

从1~5，走不同的路径也是不同的方案数。

1 2 3
    5

这样走，可以任意拿2个，答是C42。

 2 3
   5

这样走，答案是C23 = 3

   3
   5

这样只有1种走法
3

1
2   5

这样有C23 = 3种取法

1
     5

这样算1种

. 1 5

这样1种
总共C24 + 3 + 3 + 1 + 1 = 14种。

---

f[i][j][k][c]表示当前在[i.j]位置处，拿了k个物品，且最后一个物品的价值是c时的方案数
共分4种情况讨论：到当前位置是，可以不拿当前物品，也可以拿当前物品。拿的话需要保证严格递增。到当前位置有两种走法，一种是从上往下，另一种是从左往右。这样2*2 = 4种情况，需要对这四种情况分别研究。

不取当前位置物品是最简单的，就是等于左边和上面的方案数的和
左边：f[i][j][k][c] = (f[i][j][k][c] + f[i][j-1][k][c]) % MOD
上边：f[i][j][k][c] = (f[i][j][k][c] + f[i-1][j][k][c]) % MOD

取当前物品时，当前的dp是f[i][j][k][c]，需要保证

前一个维度k-1合法当前位置的物品的价值要恰好是c.(c的含义就是取得最后一个物品价值为c)前面的所有方案数取的最后一个物品的价值必须严格小于c才能将c拿起。

val = f[i][j][k][v]
 if(u > 0 && v==w[i][j]) //枚举取当前[i,j]位置上的物品 当前物品的价值必须等于v
  {
      for(int c=0;c 
ACCODE
 
#include
#include
#include
using namespace std;
const int N = 52;
int MOD = 1000000007;
int n,m,k;
int w[N][N];
int f[N][N][13][14]; //f[i][j][k][c]表示走到坐标为[i,j] 且取了k个数 且最后一个物品的价值是c的合法的方案数
//开14的原因是因为-1~12共14个数。因为价值可以是0，初始价值要最小，所以取-1 然后给所有价值+1，0~13共14个数
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++)   //枚举x y坐标
        {
            if(i==1&&j==1) continue;
            for(int u=0;u<=k;u++)   //枚举选了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]) //枚举取当前[i,j]位置上的物品 当前物品的价值必须等于v
                    {
                        for(int c=0;c					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5703308.html