hihoCoder 1476 矩形计数 dp

时间限制: 10000ms 单点时限: 1000ms 内存限制: 256MB

描述

如图所示，在由N行M列个单位正方形组成的矩形中，有K个单位正方形是黑色的，其余单位正方形是白色的。  

你能统计出一共有多少个不同的子矩形是完全由白色单位正方形组成的吗？

输入

第一行三个整数:N, M和K。

之后K行每行包括两个整数R和C，代表一个黑色单位正方形的位置。

1 <= N，M <= 1000  

1 <= K <= 10  

1 <= R <= N  

1 <= C <= M

输出

输出一个整数表示满足条件的子矩形个数。

样例输入

3 3 1
2 3       

样例输出

24      

思路

•    我们通过dp来求解这个问题。我们定义dp(i,j)表示前以(1, 1)作为左上角，（i, j）作为右下角构成的子矩阵所具有的矩形个数。
•    递推的时候，基于简单的容斥原理思想，不难发现：dp(i,j) = dp(i-1, j) + dp(i, j-1) - dp(i-1, j-1) + 用（i, j）作为右下角的子矩形个数
•    递推式的前三项的运算得到的是不用（i, j）作为右下角的子矩形个数，而最后一项则需要稍微复杂一些的计算得到。
•    注意到：用（i, j）作为右下角的子矩形个数 = 可以作为左上角的小格子个数，而“ 可以作为左上角的小格子个数”受(i, j)左上方的小黑格影响。
•    若(i, j)左上方只有一个小黑格b1位于(x1, y1)，那么“ 可以作为左上角的小格子个数” = i * j - x1 * y1
•    若还有一个小黑格b2位于(x2, y2)，若b2 处于 b1的左上方（称为b2被b1遮挡），即x2 < x1, y2 < y1，则b2就不会发挥任何作用，即“ 可以作为左上角的小格子个数” 依然等于 i * j - x1 * y1
•    因此，我们只需关心互相不被遮挡的且位于（i, j）左上方的小黑格即可，通过画图不难发现，这些小黑格一定位于不同行和不同列上，布局类似反对角线，当我们找到这些小黑格后，计算“ 可以作为左上角的小格子个数” 就比较简单了，式子就不再列出了，可以参看后面的源码。
•    所以，接下来的问题就是如何找到这些互不遮挡的小黑格了。由于小黑格个数很少，我们可以遍历它们。具体方法应该挺多的，这里我为了实现简单一些，使用了类似单调栈的思想。预处理所有小黑格，以行x为第一优先级，列y为第二优先级，升序排序，这样我保证在遍历的时候，后面的小黑格一定不会被前面的小黑格遮挡。再加上这些互不遮挡的小黑格满足这样的性质：任取其中两个小黑格（xi, yi）和（xj, yj）若xi < xj， 则yi > yj。我们制定如下策略，当遍历到bi，假如栈空或bi不遮挡栈顶元素，就bi入栈；若遮挡，则弹出栈顶，继续判断，直至不遮挡或栈空为止，把bi入栈。
• 另外这个题还可以通过容斥原理求解，大家可以参看：点击打开链接

实现

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
ll dp[maxn][maxn];
vector<pii> vec;
stack<pii> sta;
int n,m,k;
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m>>k;
	for (int i=0;i<k;i++){
		int x,y;
		cin>>x>>y;
		dp[x][y] = 1;
		vec.pb(mp(x,y));
	}
	sort(vec.begin(),vec.end());
	int cnt = 0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			bool flag = dp[i][j];
			dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
			if (flag)
			{
				cnt += flag;
				continue;
			}
			for (int t=0;t<cnt;t++){
				if (vec[t].fi > i || vec[t].se > j){
					continue;
				}
				while (sta.size() && sta.top().se <= vec[t].se){
					sta.pop();
				}
				sta.push(vec[t]);
			}
			ll sum = i * j;
			int pre_y = 0;
			while (sta.size()){
				int x = sta.top().fi;
				int y = sta.top().se;
				sta.pop();
				sum -= (y-pre_y) * x;
				pre_y = y;
			}
			dp[i][j] += sum;
		}
	}
	cout << dp[n][m] << endl; 
	return 0;
}