题解 P2956 【[USACO09OCT]机器人犁田The Robot Plow】

KesdiaelKen · 2017-08-12 06:55:11 · 题解

这一题还是很明显可以用差分来做的。差分的思想如果有意了解可以在网上搜寻资料，在这里简单讲一下，不做详细介绍——用O(1)的时间复杂度来表示O(N)的覆盖操作，具体见程序。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
int cf[1010][1010]={0};
int main()
{
    int n,m;
    cin>>n>>m;
    int gs;cin>>gs;
    int a,b,aa,bb;
    for(int i=0;i<gs;i++)
    {
        scanf("%d%d%d%d",&a,&b,&aa,&bb);
        for(int j=a;j<=aa;j++)//每行做一次差分

{//设b[i]=a[i]-a[i-1]

            cf[j][b]++;
            cf[j][bb+1]--;//前后分别加一，减一，即可代表a的变化
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cf[i][j]+=cf[i][j-1];
            if(cf[i][j])sum++;//如果已被犁到，则计数
        }
    }
    printf("%d",sum);
    return 0;
}