动态规划记录 [动态更新]

简介: 2021 江西省赛A题目链接:https://ac.nowcoder.com/acm/contest/21592/A题意:给出一个布尔矩阵(每个位置的值非零即一)然后问给定p和q,问从(1,1)=》(n,m)的所有路径中至少通过p次0&&q次1的路径的数量
  1. 2021 江西省赛A
    题目链接:https://ac.nowcoder.com/acm/contest/21592/A
    题意:给出一个布尔矩阵(每个位置的值非零即一)
    然后问给定p和q,问从(1,1)=》(n,m)的所有路径中至少通过p次0&&q次1的路径的数量


const int md = 998244353;
int a[507][507];
ll dp[507][1007];
int main() {
  int n = read,m = read,p = read,q = read;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) a[i][j] = read;
  }
  dp[1][!a[1][1]] = 1;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      if(i != 1 || j != 1)
      if(a[i][j] == 1) {
        for(int k=i+j-1; k>=0; k--) dp[j][k] = (dp[j][k] + dp[j-1][k]) % md;
      } else {
        for(int k=i+j-1; k>=1; k--) dp[j][k] = (dp[j][k-1] + dp[j-1][k-1]) % md;
        dp[j][0] = 0;
      }
    }
  }
  ll ans = 0;
  for(int i=p; i<=n+m-1-q; i++) ans = (ans + dp[m][i]) % md;
  cout << ans << endl;
  return 0;
}


文章知识点与官方知识档案匹配,可进一步学习相关知识

算法技能树leetcode-动态规划22-括号生成8282 人正在系统学习中

目录
相关文章
|
9月前
|
SQL JavaScript 数据库
树层级处理上万条数据优化!
树层级处理上万条数据优化!
|
机器学习/深度学习 人工智能 算法
时间复杂度O(40n*n)的C++算法:修改图中的边权
时间复杂度O(40n*n)的C++算法:修改图中的边权
|
9月前
|
Java
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
如何实现一个高效的二叉搜索树(BST)?请给出时间复杂度分析。 要求:设计一个二叉搜索树,支持插入、删除和查找操作。要求在平均情况下,这些操作的时间复杂度为O(log n)。同时,考虑树的平衡性,使得树的高度保持在对数级别。
80 0
|
8月前
|
算法 搜索推荐
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
数据结构和算法——表排序(算法概述、物理排序、复杂度分析,包含详细清晰图示过程)
73 0
|
存储 算法
算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
算法训练Day18|● 513.找树左下角的值● 112. 路径总和 113.路径总和ii● 106.从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树
算法训练Day18|● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和
算法训练Day18|● 110.平衡二叉树 ● 257. 二叉树的所有路径 ● 404.左叶子之和
|
前端开发
前端学习案例1-二叉搜索树删除两个节点的情况1
前端学习案例1-二叉搜索树删除两个节点的情况1
105 0
前端学习案例1-二叉搜索树删除两个节点的情况1
|
前端开发
前端学习案例2-二叉搜索树删除两个节点的情况2
前端学习案例2-二叉搜索树删除两个节点的情况2
91 0
前端学习案例2-二叉搜索树删除两个节点的情况2
|
算法
删除链表中间节点(变形题目,简单难度)
删除链表中间节点(变形题目,简单难度)
102 1
删除链表中间节点(变形题目,简单难度)
|
算法 Java
【算法】字符串复原IP地址,从前序与中序编辑序列构造二叉树 三道算法题
字符串复原IP地址,从前序与中序编辑序列构造二叉树
141 1
【算法】字符串复原IP地址,从前序与中序编辑序列构造二叉树 三道算法题

热门文章

最新文章