题目大意
现在有个人站在第 \(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}\);
代码
#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