A - Mio visits ACGN Exhibition（dp）

A - Mio visits ACGN Exhibition

借鉴了：https://blog.csdn.net/qq_63010655/article/details/123699263
并做了些许优化

用dp[i][j][k]来表示 到第i行第j列，经过了k个0的所有路径数。
又可以用0和1两个状态来优化i
妙啊，orz

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define r0 return 0
#define endl "\n"
#define pii pair<int,int>
#define inf 0x3f3f3f3f
const int N = 2e5 + 5;
int g[505][505];
ll dp[2][505][10005];
const int mod = 998244353;
int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m, sum0, sum1;
	cin >> n >> m >> sum0 >> sum1;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> g[i][j];
	if (g[1][1] == 1) dp[1][1][0] = 1; // 初始化，默认第一行是1
	else if (g[1][1] == 0) dp[1][1][1] = 1; // 第三维表示0的个数 ,整体表示路径的个数
	int s = 1; //用s来优化行，每一行只需要不一样就可以了所以用0和1来表示.
	// 默认第一行是1
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (i == 1 && j == 1) continue;
			for (int k = 0; k <= i + j - 1; k++)
			{
				if (g[i][j] == 0)
				{ 
					if (k == 0) dp[s][j][k] = 0; //这里记得赋值，因为必须覆盖掉上一行的
					else
					dp[s][j][k] = (dp[s ^ 1][j][k - 1] + dp[s][j - 1][k - 1])%mod;
				}
				else
				{
					dp[s][j][k] = (dp[s ^ 1][j][k] + dp[s][j - 1][k])%mod;
				}

			}
		}
		s ^= 1; // 换行
	}
	s ^= 1; // 多换了一次，换回来
	int ans = 0;
	for (int k = sum0; n + m - 1 - k >= sum1; k++)
	{
		ans = (ans + dp[s][m][k]) % mod;

	}
	cout << ans << endl;
	r0;
}