Zero Path（1700）

题目大意：给定n*m方阵，每个格点上有1或-1。每次只能向右移动一步或者向下移动一步。问是否存在从起始点(1,1)到(n,m)一条和为0的路径。
思路：
关键在于充分利用方阵上的-1,1，增量时仅会造成很小变化，可能在变化的途中达到目标值。（先找到某个范围）

从起点到终点走的格点数是固定的，都是n+m-1。因此n+m-1为奇数时，不可能达成目标。而n+m-1为偶数时，由于奇+奇=偶，奇-奇=偶，因此到达(n,m)点的所有路径和都为偶数。
使用dp容易求得路径和的最大值和最小值(必要条件)。如果[最小值，最大值]包含0，则最终答案包含0。这是因为可以移动每次上下水平向右移动的步骤使得路径和变为最大值。使用方阵上的-1，1的条件，每次移动改变路径和-2或2。于是一定某次移动后路径和变为0
反思：这种思想以前是遇到过的，见那个很妙的滑动窗口均值的题(juju and binary string 2800)。
另一种思路：运用bitset dp记录和。

#include <bits/stdc++.h>
using namespace std;
vector<bool> vis;


int main()
{
    
    int t; cin>>t;
    for(int i  =0 ;i<t;i++)
    {
    
        int n,m;
        scanf("%d %d",&n,&m);
        int d[n][m];
        for(int  k = 0;k<n;k++) for(int q = 0;q<m;q++) scanf("%d",&d[k][q]);
        if((n+m-1)%2==1) {
    printf("NO\n");continue;}
        int dpmin[n][m],dpmax[n][m];
        dpmin[0][0]=dpmax[0][0]=d[0][0];
        for(int i = 0;i<n;i++)
        {
    
            for(int j = 0;j<m;j++)
            {
    
                if(i==0&&j==0) continue;
                int a = INT_MIN;  //用于更新最大值
                int b = INT_MAX;  //用于更新最小值
                if(i-1>=0) {
    a = max(a,dpmax[i-1][j]); b = min(b,dpmin[i-1][j]);}
                if(j-1>=0) {
    a = max(a,dpmax[i][j-1]);    b = min(b,dpmin[i][j-1]);}
                dpmax[i][j] = a + d[i][j];
                dpmin[i][j] = b + d[i][j];
            }
        }
        if(dpmin[n-1][m-1]<=0 && dpmax[n-1][m-1]>=0) printf("YES\n"); else printf("NO\n");
    }
    system("pause");
}