CF729B Spotlights 题解

题目简述

给出一个 $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;
}