【codeforces 1695C Zero Path】DP

Topic link

The question ：

To give you one n*m Matrix , The value of each number of this matrix is 1 Or is it -1, Ask whether there is a path so that the sum on the path is 0, Each point can only go down one grid or go right one grid

analysis ：

First of all, the length of this path must be n+m-1, So if the length is an odd number, there must be no solution , Because it's all 1 Or is it -1, When the length is even , use mx[i][j] From (1,1) To (i,j) The maximum value of the path ,mi[i][j] From (1,1) To (i,j) The minimum value of the path , And then if 0 stay mx[n][m] and mi[n][m] Then there must be a solution , because mx[n][m] and mi[n][m] It must be an even number , Then the path can be transformed to make mx[n][m] and mi[n][m] To change in real time , And the range of change is 2, So as long as it's 0 Within the range, it must be able to obtain , Now look at the code ：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010,inf = 1e7;
int g[N][N];
int mx[N][N],mi[N][N];
typedef pair<int,int> PII;
int main(){
    
	int T;
	cin>>T;
	while(T--){
    
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
    
				scanf("%d",&g[i][j]);
				mx[i][j] = -1e7;
				mi[i][j] = 1e7;
			}
		if((n+m-1)%2){
    
			cout<<"NO"<<endl;
			continue;
		}
		mx[1][1] = mi[1][1] = g[1][1];
		for(int i=1;i<=n;i++){
    
			for(int j=1;j<=m;j++){
    
				if(i > 1){
    
					mx[i][j] = max(mx[i][j],mx[i-1][j]+g[i][j]);
					mi[i][j] = min(mi[i][j],mi[i-1][j]+g[i][j]);
				}
				if(j > 1){
    
					mx[i][j] = max(mx[i][j],mx[i][j-1]+g[i][j]);
					mi[i][j] = min(mi[i][j],mi[i][j-1]+g[i][j]);
				}
			}
		}
		if(mx[n][m] >= 0 && mi[n][m] <= 0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	
	return 0;
}