洛谷1578：[WC2002]奶牛浴场—

https://www.luogu.org/problemnew/show/P1578#sub

由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显然不能在浴场中产奶，于是，John希望所建造的浴场不覆盖这些产奶点。这回，他又要求助于Clevow了。你还能帮助Clevow吗？

John的牛场和规划的浴场都是矩形。浴场要完全位于牛场之内，并且浴场的轮廓要与牛场的轮廓平行或者重合。浴场不能覆盖任何产奶点，但是产奶点可以位于浴场的轮廓上。

Clevow当然希望浴场的面积尽可能大了，所以你的任务就是帮她计算浴场的最大面积。

（其实并不知道是不是WC2002的题目emm）

请食用王知昆论文：http://blog.csdn.net/twtsa/article/details/8120269，和洛谷第一篇题解。

这里使用的是算法1（并不知道什么名字，枚举法？）

然而那篇题解虽然指出了很多bug的所在以及解决方法，但是代码变量名（自我感觉）很不友好。

我觉得我的代码还是很清真emm。

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<vector>

#include<algorithm>

using namespace std;

const int N=;

inline int read(){int x;scanf("%d",&x);return x;}

struct node{

    int x,y;

}a[];

bool cmp1(node a,node b){

    return a.x<b.x||(a.x==b.x&&a.y<b.y);

}

bool cmp2(node a,node b){

    return a.y<b.y;

}

int main(){

    int n=read(),m=read();

    int s=read();

    for(int i=;i<=s;i++)a[i].x=read(),a[i].y=read();

    a[++s].x=;a[s].y=;a[++s].x=n;a[s].y=;

    a[++s].x=;a[s].y=m;a[++s].x=n;a[s].y=m;

    sort(a+,a+s+,cmp1);

    int ans=;

    for(int i=;i<=s;i++){

    int l=,r=m,v=n-a[i].x;

    for(int j=i+;j<=s;j++){

        if(l<=a[j].y&&a[j].y<=r){

        if(v*(r-l)<=ans)break;

        ans=max(ans,(a[j].x-a[i].x)*(r-l));

        if(a[i].y==a[j].y)break;

        if(a[j].y>a[i].y)r=min(r,a[j].y);

        else l=max(l,a[j].y);

        }

    }

    l=,r=m,v=a[i].x;

    for(int j=i-;j>=;j--){

        if(l<=a[j].y&&a[j].y<=r){

        if(v*(r-l)<=ans)break;

        ans=max(ans,(a[j].x-a[i].x)*(r-l));

        if(a[i].y==a[j].y)break;

        if(a[j].y>a[i].y)r=min(r,a[j].y);

        else l=max(l,a[j].y);

        }

    }

    }

    sort(a+,a+s+,cmp2);

    for(int i=;i<=s-;i++)ans=max(ans,(a[i+].y-a[i].y)*n);

    printf("%d\n",ans);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

洛谷1578：[WC2002]奶牛浴场——题解

最新文章

热门文章