2021 ICPC 江西省大学生程序设计竞赛 A.Mio visits ACGN Exhibition DP+降维优化

题目大意：给定一个 n × m n \times m n×m的 0 − 1 0-1 0−1矩阵，要求从左上角 ( 1 , 1 ) (1,1) (1,1)走到右下角 ( n , m ) (n, m) (n,m)，路径上至少经过 p p p个 0 0 0， q q q个 1 1 1。求这样的路径有多少条。

思路分析： D P DP DP思路是队友给的，贴一个队友的博客：2021 ICPC 江西省 A. Mio visits ACGN Exhibition（DP，大离谱，经验分享）_yezzz的博客-CSDN博客

首先按照 D P DP DP的基本思路，用 d p [ i ] [ j ] [ x ] [ y ] dp[i][j][x][y] dp[i][j][x][y]表示到 ( i , j ) (i, j) (i,j)位置，走过了 x x x个 0 0 0和 y y y个 1 1 1。然后考虑数据规模，显然空间会爆掉(需要开 l o n g   l o n g long\ long long long)，那么考虑降维优化：

• y y y可以被压缩，因为由 ( 1 , 1 ) → ( i , j ) (1, 1) \rightarrow (i, j) (1,1)→(i,j)经过了 i + j i + j i+j步，其中有 x x x个 0 0 0，那么 y = i + j − 1 − x y = i + j - 1 - x y=i+j−1−x，即 y y y可以用前三维表示；

那么 d p [ i ] [ j ] [ x ] dp[i][j][x] dp[i][j][x]就可以表示到 ( i , j ) (i, j) (i,j)位置，走过了 x x x个 0 0 0和 i + j − 1 − x i + j - 1 - x i+j−1−x个 1 1 1。我们可以得出状态转移方程： d p [ i ] [ j ] [ x ] = { d p [ i ] [ j − 1 ] [ x ] + d p [ i − 1 ] [ j ] [ x ] ,   ( m p [ i ] [ j ] = = 1 ) d p [ i ] [ j − 1 ] [ x − 1 ] + d p [ i − 1 ] [ j − 1 ] [ x − 1 ] ,   ( m p [ i ] [ j ] = = 0 ) dp[i][j][x]= \begin{aligned} \begin{cases} dp[i][j - 1][x] + dp[i - 1][j][x],\ (mp[i][j] == 1) \\ dp[i][j - 1][x - 1] + dp[i - 1][j - 1][x - 1],\ (mp[i][j] == 0) \\ \end{cases} \end{aligned} dp[i][j][x]={dp[i][j−1][x]+dp[i−1][j][x], (mp[i][j]==1)dp[i][j−1][x−1]+dp[i−1][j−1][x−1], (mp[i][j]==0)​​

• 空间仍然不是最优的，仍然会卡空间。考虑继续降维优化：不难发现，自顶开始向下，每一行的状态在当前的循环中只会影响下一轮的状态，于是可以采用滚动数组法优化掉第一维度。 d p [ j ] [ x ] = { d p [ j − 1 ] [ x ] + d p [ j ] [ x ] ,   ( m p [ i ] [ j ] = = 1 ) d p [ j − 1 ] [ x − 1 ] + d p [ j − 1 ] [ x − 1 ] ,   ( m p [ i ] [ j ] = = 0 ) dp[j][x]= \begin{aligned} \begin{cases} dp[j - 1][x] + dp[j][x],\ (mp[i][j] == 1) \\ dp[j - 1][x - 1] + dp[j - 1][x - 1],\ (mp[i][j] == 0) \\ \end{cases} \end{aligned} dp[j][x]={dp[j−1][x]+dp[j][x], (mp[i][j]==1)dp[j−1][x−1]+dp[j−1][x−1], (mp[i][j]==0)​​

注意处理细节，极其容易被卡。

#include 
#define int long long
#define MOD 998244353
using namespace std;

const int N = 1000 + 10;
int mp[N][N], dp[N][N], sto[N][N];

inline void solve(int ans = 0){
    int n, m, p, q; cin >> n >> m >> p >> q;
    for(int i = 1; i  mp[i][j];
    (!mp[1][1]) ? dp[1][1] = 1 : dp[1][0] = 1;
    for(int i = 1; i