题目简述
给出一个 $n$ 行 $m$ 列的 $01$ 矩阵，定义每个点的价值为上下左右四个方向有 $1$ 的方向数，求所有为 $0$ 的点的价值和。
题目分析
我们首先可以考虑暴力，但是发现是不行的。于是我们考虑动态规划。
设 $dp_{i,j,0/1/2/3}$ 分别表示 $(i,j)$ 这个点上方，左方，下方，右方是否有 $1$。接下来考虑如何转移，我们先考虑上方，显然当 $a_{i-1,j}=1$ 时，$dp_{i,j,1} \leftarrow 1$。如果 $dp_{i-1,j,1}=1$，这也说明 $(i,j)$ 上方有 $1$，所以也有 $dp_{i,j,1} \leftarrow 1$。知道了上方怎么转移，那么其他三个方向也是一样的道理。但是要注意左方和下方的转移顺序。时间复杂度 $\mathcal{O}(n \times m)$，可以通过。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
const int N=1010;
int n,m,a[N][N],ans,dp[N][N][4];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cin>>n>>m;For(i,1,n){For(j,1,m){cin>>a[i][j];}} For(i,1,n){For(j,1,m){if(!a[i][j]){dp[i][j][0]=dp[i-1][j][0]|a[i-1][j];//利用位运算精简一下dp[i][j][1]=dp[i][j-1][1]|a[i][j-1];ans+=dp[i][j][0]+dp[i][j][1];}}}Rep(i,n,1){Rep(j,m,1){if(!a[i][j]){dp[i][j][2]=dp[i+1][j][2]|a[i+1][j];dp[i][j][3]=dp[i][j+1][3]|a[i][j+1];ans+=dp[i][j][2]+dp[i][j][3];}}}cout<<ans;return 0;
}
