首页 > 其他分享 >P8707 [蓝桥杯 2020 省 AB1] 走方格

P8707 [蓝桥杯 2020 省 AB1] 走方格

时间:2023-02-25 08:33:58浏览次数:54  
标签:P8707 int 行第 蓝桥 AB1 2020 这一格

题目传送门

题目大意

现在有个人站在第 \(1\) 行第 \(1\) 列,要走到第 \(n\) 行第 \(m\) 列(只能向右或者向下走),如果行号和列数都是偶数,不能走入这一格中。

问有多少种方案。

解题思路

方法一:从 \(f_{1,1}\) 推到 \(f_{n,m}\):

  • 划分阶段:以当前的方案数为阶段;

  • 状态表达:设 \(f_{i,j}\) 表示走到第 \(i\) 行,第 \(j\) 列时的方案数;

  • 初始状态:\(f_{i,1}=1,f_{1,j}=1\);

  • 转移方程:\(f_{i,j}=f_{i-1,j}+f_{i,j-1}\)(在可以走入这一格的情况下);

  • 求解目标:\(f_{n,m}\);

代码

AC 记录

#include<bits/stdc++.h>
#define ri register int
using namespace std;
int n,m,f[35][35];
int main() {
	cin>>n>>m;
	for(ri i=1;i<=n;i++)f[i][1]=1;
	for(ri j=1;j<=m;j++)f[1][j]=1;
	//从起始点到第一行和第一列的方案数都为 1 
	for(ri i=2;i<=n;i++){
		for(ri j=2;j<=m;j++){
			if(i%2==0&&j%2==0)f[i][j]=0;//不能进入:将方案数赋为 0 
			else f[i][j]=f[i-1][j]+f[i][j-1];//能进入:计算从左和从上走到当前位置的方案数 
		}
	}
	cout<<f[n][m];//输出答案 
	return 0;
}

标签:P8707,int,行第,蓝桥,AB1,2020,这一格
From: https://www.cnblogs.com/zzyblog0619/p/17153716.html

相关文章

  • P8709 [蓝桥杯 2020 省 A1] 超级胶水
    题目传送门题目大意有\(n\)个石子,两颗石子的重量之和就是并成的一颗新石子的重量,合并两个石子需要的胶水等于两颗石子重量的乘积。解题思路先将\(sum\)赋为第一个......
  • P8717 [蓝桥杯 2020 省 AB2] 成绩分析 题解
    题目传送门题目大意计算\(n\)个人考试的最高分、最低分和平均分。解题思路输入\(n\)个人成绩的同时,计算最大值,最小值和总数。再将总数除以\(n\)算出平均值并保......
  • [羊城杯 2020]ByteCode writeup
    下载附件打开:  可以判断为是Python字节码,按照逻辑手动反编译出源码来即可,逻辑并不复杂,有不懂的地方可以看参考文献还原出来的源码为:#flag=input("pleaseinput......
  • 蓝桥杯2022年第十三届省赛真题-回忆迷宫 (暴力加深搜)
    题目描述爱丽丝刚从一处地下迷宫中探险归来,你能根据她对于自己行动路径的回忆,帮她画出迷宫地图吗? 迷宫地图是基于二维网格的。爱丽丝会告诉你一系列她在迷宫中的......
  • 2023.2.23AcWing蓝桥杯集训·每日一题
    今天练习的思维为递推。AcWing3777.砖块题目描述\(n\)个砖块排成一排,从左到右编号依次为\(1∼n\)。每个砖块要么是黑色的,要么是白色的。现在你可以进行以下操作若......
  • Matlab 2020a 中文破解版软件包下载及图文安装教程​
    MATLAB是美国MathWorks公司出品的商业数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语......
  • Matlab 2020b 中文破解版软件包下载及图文安装教程​
    MATLAB是美国MathWorks公司出品的商业数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。行矩阵运算、绘制函数和数据、实现算法、创建用户界面、连接其他编程语......
  • CTT 2020 部分记录
    想了想还是分开写(感觉自己落了很多题啊,退役前都补不完了day1T1:感觉像是k线性基板子,但我又不怎么会day3T1:看到神秘的条件感觉不太好dp,但可以算\(\sum(-1)^{val......
  • 2023.2.22AcWing蓝桥杯集训·每日一题
    知识点为双指针。AcWing1238.日志统计(蓝桥杯辅导课)题目描述小明维护着一个程序员论坛。现在他收集了一份”点赞”日志,日志共有\(N\)行。其中每一行的格式是:tsid......
  • 蓝桥杯学习笔记(一)
    蓝桥杯学习笔记(一)零碎知识点:输入输出的数据<105使用cincout输入输出的数据>=105使用scanfprintf220≈106 216=65536 215=32268 263≈1018头文件大......