Codeforces Round #801 (Div. 2) C(规律证明)
题目链接：
传送门QAQ
题意：
给定一个\(n * m\)的矩阵，矩阵的每个单元的值为1或-1，问从\((1,1)\)开始出发，每次只可以向下和向右走，问到终点\((n * m)\)时，是否可以总值为1。
分析：
题意很简单，本题的重点是在于，是否知道一个这样的结论:
首先定义 \(mn[i][j]\)为在\((i,j)\)处能拿到最少数量的1。
\(mx[i][j]\)为在\((i,j)\)处能拿到最多数量的1。
结论：走到\((i,j)\)处可以拿的1的数量\(sum\)，有
\[mn[i][j] \leqslant sum \leqslant mx[i][j]
\]
证明:首先\((1，1)\)处显然成立，假设在\((i,j)\)处同样成立，那么对于\((i+1,j)\)处，显然他是由\((i,j)\)和\((i,j-1)\)转移过来，所以无论\(a[i][j]\)是否为1，都成立，同理可以去证明，\((i,j+1)\)处和\((i+1,j+1)\)处也成立，根据归纳法，该结论对于任意\((i,j)\)都成立。
代码：
void solve(){
cin >> n >> m;
for (int i = 1;i <=n;i ++) {
for (int j = 1;j <= m;j ++) {
cin >> a[i][j];
if(a[i][j] == -1) a[i][j] = 0;
mn[i][j] = 0;
mx[i][j] = 0;
}
}
if((n + m - 1) % 2 == 1) {
cout << "NO" << endl;
return ;
}
mn[1][1] = mx[1][1] = (a[1][1] == 1);
for (int i = 1;i <= n; i++) {
for (int j = 1;j <= m;j ++) {
if(i == 1 && j == 1) continue;
if(j == 1) {
mn[i][j] = mn[i-1][j] + a[i][j];
mx[i][j] = mn[i-1][j] + a[i][j];
}
else if(i == 1) {
mn[i][j] = mn[i][j-1] + a[i][j];
mx[i][j] = mn[i][j-1] + a[i][j];
}
else {
mx[i][j] = max(mx[i-1][j] , mx[i][j-1]) + a[i][j];
mn[i][j] = min(mn[i][j-1] , mn[i-1][j]) + a[i][j];
}
}
}
int ans = (n + m - 1) / 2;
if(ans >= mn[n][m] && ans <= mx[n][m]) cout << "YES" << endl;
else cout << "NO" << endl;
}
