Mio visits ACGN Exhibition（2021江西省icpc省赛A题）

题目

Mio visits ACGN Exhibition

问题描述

给定一个$n$行$m$列的矩阵空间，内部存在$n?m$个方格，而每个方格对应物品$0或1$，同时给定数据$p$跟$q$。
此时人物从左上角的$[1,1]$走到右下角$[n,m]$,要求人物每次只能选择向下走或者是向右走，每次仅可以移动一个方格，每抵达一个方格就获得该方格的物品，问存在多少种路径可以使得人物抵达$[n,m]$时，获得的物品$0$不少于$p$,获得的物品$1$不少于$q$.
$1\le n,m\le 500$
$1\le p,q\le 10000$

分析

首先分析题目，在一条路径中人物所可以获得的物品的总数目为$n+m?1$
这也就意味着$p,q$必须满足$p+q\le n+m?1$,否则情况一定是不存在的。

题目的思路是动态规划，此时第一个问题是确定状态，一开始很直观的状态的是一个四维状态$dp[i][j][p][q]$表明抵达位置$[i,j]$时物品$0$等于$p$,物品$1$等于$q$的方法数，先不考虑递推公式的写法，单单是这个空间就会爆掉$O(n?m?(n+m{)}^2)$,所以需要将状态进行简化.

我们已知$p+q\le n+m?1$，在一个位置已知当前已经获得的物品$0$的个数，当然可以反推出已经获得物品$1$的个数，那么我们就可以把四维状态优化为三维，此时$dp[i][j][k]$表示位置$[i,j]$的获得物品$0$的个数恰好为$k$的路径数，那么我们最后的结果也就是统计${\sum }_{k=p}^{n+m?1?q}dp[n][m][k]$的值(k最少为p个，最多为n+m-1-q个，不影响物品1).

递推公式：
$$\{\begin{array}{l}(i,j)=0,dp[i][j][k]=dp[i?1][j][k?1]+dp[i][j?1][k?1]\\ (i,j)=1,dp[i][j][k]=dp[i?1][j][k]+dp[i][j?1][k]\end{array}$$
此时的空间仍然过大，需要采用滚动数组来简化。

注意：
1.对于$[1,1]$单独处理，作为边界点

if(a[1][1])dp[1][1][0]=1;else dp[1][1][1]=1;

2.当$a[i,j]==0$时，这个点就不会存在k为0的情况1，因为本身就带有一个物品0，所以要将$dp[1][j][0]$置为0，并且循环从k=1开始，以免越界。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=510;
const int mod=998244353;
const int M=1010;
int dp[2][N][M];
int a[N][N];
int main(){
    int n,m,p,q;cin>>n>>m>>p>>q;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j];if(a[1][1])dp[1][1][0]=1;else dp[1][1][1]=1;for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
    if(i==1&&j==1)continue;if(a[i][j]){
    for(int k=0;k<M;k++){
    dp[1][j][k]=(dp[1][j-1][k]+dp[0][j][k])%mod;}}else{
    dp[1][j][0]=0;for(int k=1;k<M;k++){
    dp[1][j][k]=(dp[1][j-1][k-1]+dp[0][j][k-1])%mod;}}}for(int j=1;j<=m;j++){
    for(int k=0;k<M;k++)dp[0][j][k]=dp[1][j][k];}}int ans=0;for(int i=p;i<=n+m-1-q;i++){
    ans=(ans+dp[0][m][i])%mod;}	cout<<ans;return 0;
}