luogu1578 奶牛浴场 枚举点最大子矩阵
2024-08-30 04:40:09
建议看看王知昆dalao的论文，讲得很好
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int l, w, n, ans=0, sh, xi, ma;
struct Node{
int x, y;
}nd[5105];
bool cmp1(Node u, Node v){
return u.y<v.y;
}
bool cmp2(Node u, Node v){
if(u.x==v.x) return u.y<v.y;
return u.x<v.x;
}
int main(){
cin>>l>>w>>n;
for(int i=1; i<=n; i++)
scanf("%d %d", &nd[i].x, &nd[i].y);
nd[++n] = (Node){0, 0};
nd[++n] = (Node){l, 0};
nd[++n] = (Node){0, w};
nd[++n] = (Node){l, w};
sort(nd+1, nd+1+n, cmp1);
for(int i=1; i<n; i++)
ans = max(ans, (nd[i+1].y-nd[i].y)*l);
sort(nd+1, nd+1+n, cmp2);
for(int i=1; i<=n; i++){
sh = w; xi = 0; ma = l - nd[i].x;
for(int j=i+1; j<=n; j++)
if(nd[j].y<=sh && nd[j].y>=xi){
if(ma*(sh-xi)<=ans) break;
ans = max(ans, (nd[j].x-nd[i].x)*(sh-xi));
if(nd[j].y==nd[i].y) break;
else if(nd[j].y>nd[i].y) sh = nd[j].y;
else xi = nd[j].y;
}
sh = w; xi = 0; ma = nd[i].x;
for(int j=i-1; j>=1; j--){
if(nd[j].y<=sh && nd[j].y>=xi){
if(ma*(sh-xi)<=ans) break;
ans = max(ans, (nd[i].x-nd[j].x)*(sh-xi));
if(nd[j].y==nd[i].y) break;
else if(nd[j].y>nd[i].y) sh = nd[j].y;
else xi = nd[j].y;
}
}
}
cout<<ans<<endl;
return 0;
}
最新文章
- python面向对象编程
- maxiang conf
- Xamarin.IOS之多视图
- linux笔记：权限管理-sudo
- Android学习七：new Date使用
- C#...何时需要重写ToString()方法?
- C语言的变量的内存分配
- Asp.Net项目与TCP服务端交互
- dbus 消息和消息总线实例讲解-一
- Django Model模型的实战操作笔记
- delphi 的 LockType 锁类型
- Linux系统——Nginx反向代理与负载均衡
- perl6 Net::HTTP 不能发送https请求
- 为apache安装mod_wsgi的时候出现-fpic的问题
- php学习十四：抽象，接口和多态
- windows 10上利用Microsoft RTF文件（CVE-2017-0199）进行攻击
- Numpy 数据分析基础
- (转)linux shell 数字计算详解
- Java框架安全
- Delphi中CPort控件之Timeout属性