题目背景
$阳先生在一片空地上行走,他很有原则,只可以沿直线向下或向右行走。$
$每拐弯一次就会让自己的羞耻感+1。$
题目描述
$现在给你阳先生可以容忍的最大羞耻值。$
$试求在最大羞耻值内阳先生有多少条路可以从(1,1)号点,走到(n,m)号点。$
$注意:一开始选择的方向不会增加阳先生的羞耻感$
输入格式
$输入n,m,k。$
$n,m代表地图的大小,k代表阳先生最大可容忍的羞耻值。$
输出格式
$输出在最大羞耻值内阳先生有多少条路可以从(1,1)号点,走到(n,m)号点。(答案对998244353取模)$
样例 #1
样例输入 #1
2 3 2
样例输出 #1
3
样例 #2
样例输入 #2
5 5 1
样例输出 #2
2
提示
$数据范围:$
1<n,m,k<100
$样例1的2*3矩形$
000
000
$对于样例1,在2*3的矩形中,有这三条路可以走:$
111
001 //拐一次弯
110
011 //拐两次弯
100
111 //拐一次弯
先看状态表示
$f[i][i][k][0] 表示在第1行j列中第k次转弯并且最后一次是向右走$
$f[i][i][k][1] 表示在第1行j列中第k次转弯并且最后一次是向下走$
状态转移
(i , j)位置中第k次转弯最后一次向右走可以从 其上面位置的第k次转弯并且最后一次向右和第k-1次转弯并且最后一次下转移来的
f[i][j][k][0] = f[i][j-1][k][0] + f[i][j-1][k-1][1]
同理
(i , j)位置中第k次转弯最后一次向下走可以从 其左边位置的第k次转弯并且最后一次向下和第k-1次转弯并且最后一次向右转移
f[i][j][k][1] = f[i-1][j][k][1] + f[i-1][j][k-1][0]
初始设置
最左边和最右边都为1 并且从(2,2) 的位置开始,题目限制了n,m > 1 所以不用再对这层数据进行特判
代码
#include<iostream>
#include<algorithm>
#include<cstring>
/*0是向右走 1是向下走*/
using namespace std;
const int MAX = 110 , MOD = 998244353;
long long f[MAX][MAX][MAX][2];
int n , m ;
int k ;
int main(){
cin>>n>>m>>k;
for(int i = 1;i<=n;i++) f[i][1][0][1] = 1;
for(int j = 1;j<=m;j++) f[1][j][0][0] = 1;
for(int i = 2 ; i <= n ; i ++){
for(int j = 2 ; j <= m ; j ++){
for(int z = 1 ; z <= k ; z ++){
f[i][j][z][0] = (f[i][j-1][z][0] + f[i][j-1][z-1][1])%MOD;
f[i][j][z][1] = (f[i-1][j][z][1] + f[i-1][j][z-1][0])%MOD;
}
}
}
long long res = 0;
for(int i = 0 ; i <= k ; i ++){
res = (res + f[n][m][i][0] + f[n][m][i][1])%MOD;
}
cout<<res<<endl;
return 0;
}