蓝桥训练 dp 背包-白红宇的个人博客

蓝桥训练 dp 背包

发布日期：2021-05-14 16:48:45 浏览次数：18 分类：精选文章

本文共 1241 字，大约阅读时间需要 4 分钟。

X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。

地宫的入口在左上角，出口在右下角。

小明被带到地宫的入口，国王要求他只能向右或向下行走。

走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。

当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。

请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。

输入

输入一行3个整数，用空格分开：n m k (1< =n,m< =50, 1< =k< =12)

接下来有 n 行数据，每行有 m 个整数 Ci (0< =Ci< =12)代表这个格子上的宝物的价值

输出

要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。

样例输入

2 3 2

1 2 3

2 1 5

样例输出

这题目坑点还是有的，思路很简单，开4维记录状态，dp[i][j][v][k]指的是到了第i行第j列最后一个选的物品价值为v选了k个选法的数量，同时它的每个点的价值有点恶心可以取到0，这样会让不选和选0有冲突，让价值+1,就方便计算了。如果v和当前这个点的价值相等才可以取这个点，并且k>0,否则负数不合法。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            #define IL inline#define x first#define y secondtypedef long long ll;using namespace std;const int N=52;int n,m,k; int a[N][N];ll dp[N][N][14][14];const int mod=1e9+7;int main(){ cin>>n>>m>>k; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {cin>>a[i][j]; a[i][j]++; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int v=0;v<=13;v++) for(int kk=0;kk<=k;kk++) { if(i==1&&j==1) { dp[1][1][0][0]=1; dp[1][1][a[1][1]][1]=1; continue; } dp[i][j][v][kk]=(dp[i-1][j][v][kk]+dp[i][j-1][v][kk])%mod; if(v==a[i][j]&&kk>0) { for(int tt=0;tt

上一篇：问题 1445: [蓝桥杯][历届试题]最大子阵

下一篇：蓝桥训练，判断两个点是否连通

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章