关键词：
O(s2)算法
详见论文 王知昆--浅谈用极大化思想解决最大子矩形问题
我就复制你能把我怎么样QAQ
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 5010
#define max(x, y) ((x) > (y) ? (x) : (y))
#define min(x, y) ((x) < (y) ? (x) : (y))
int L, W, n, ans;
struct node
{
int x, y;
}p[N];
inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
}
inline bool cmp1(node a, node b)
{
return a.y < b.y;
}
inline bool cmp2(node a, node b)
{
return a.x < b.x;
}
int main()
{
int i, j, x, u, d;
L = read();
W = read();
n = read();
for(i = 1; i <= n; i++) p[i].x = read(), p[i].y = read();
p[++n].x = 0, p[n].y = 0;
p[++n].x = 0, p[n].y = W;
p[++n].x = L, p[n].y = 0;
p[++n].x = L, p[n].y = W;
std::sort(p + 1, p + n + 1, cmp1);
for(i = 2; i <= n; i++)
{
x = p[i].y - p[i - 1].y;
ans = max(ans, x * L);
}
std::sort(p + 1, p + n + 1, cmp2);
for(i = 1; i <= n; i++)
{
u = W;
d = 0;
for(j = i + 1; j <= n; j++)
{
if(p[j].x == p[i].x) continue;
ans = max(ans, (u - d) * (p[j].x - p[i].x));
if(p[j].y == p[i].y)
{
if(u - p[j].y > p[j].y - d) d = p[j].y;
else u = p[j].y;
}
else
{
if(p[j].y > p[i].y) u = min(u, p[j].y);
else d = max(d, p[j].y);
}
}
}
for(i = n; i >= 1; i--)
{
u = W;
d = 0;
for(j = i - 1; j >= 1; j--)
{
if(p[j].x == p[i].x) continue;
ans = max(ans, (u - d) * (p[j].x - p[i].x));
if(p[j].y == p[i].y)
{
if(u - p[j].y > p[j].y - d) d = p[j].y;
else u = p[j].y;
}
else
{
if(p[j].y > p[i].y) u = min(u, p[j].y);
else d = max(d, p[j].y);
}
}
}
printf("%d\n", ans);
return 0;
}
洛谷p1578奶牛浴场
P1578奶牛浴场题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情
p1578奶牛浴场(代码片段)
题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产奶，而奶牛显... 查看详情
洛谷1578：[wc2002]奶牛浴场——题解(代码片段)
...gu.org/problemnew/show/P1578#sub由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置... 查看详情
[wc2002][洛谷p1578]奶牛浴场
...话多呢。 题目描述由于John建造了牛场围栏，激起了奶牛的愤怒，奶牛的产奶量急剧减少。为了讨好奶牛，John决定在牛场中建造一个大型浴场。但是John的奶牛有一个奇怪的习惯，每头奶牛都必须在牛场中的一个固定的位置产... 查看详情
dp悬线法奶牛浴场(代码片段)
虽然还是悬线法，但是这道题可不能轻易地套模板了，而是要换一种思路，横着扫一遍，竖着扫一遍，时间复杂度依旧是O(n^2),然而空间复杂度有一定的优化如果用原来的方法，显然时间空间都会炸（如果你想用map我也没办法...... 查看详情
[luogup1868]饥饿的奶牛（dp）
传送门 先把所有区间按照左端点排序f[i]表示区间0~i的最优解 #include<cstdio>#include<iostream>#include<algorithm>#definemax(x,y)((x)>(y)?(x):(y))intn,v;intf[3000001];structnode{ intx,y;}p[150001]; 查看详情
luogup2344奶牛抗议(树状数组优化dp)(代码片段)
传送门 解题思路树状数组优化dp，f[i]表示前i个奶牛的分组的个数，那么很容易得出$f[i]=sumlimits_1leqjleqif[j-1]*(sum[i]gesum[j-1])$，但是这样的时间复杂度是$O(n^2)?$，所以考虑优化，发现必须满足$sum[i]gesum[j-1]?$才能进... 查看详情
[luogup1472]奶牛家谱cowpedigrees（dp）
传送门 一个深度为i的树可以由一个根节点外加两个深度为i-1的树组成，这就决定了DP该怎么写。然而我真的没有想到。 f[i][j]表示深度为i节点数为j的个数sum[i][j]表示深度小于等于i节点树为j的个数 #include<cstdio>#de... 查看详情
[luogup2915][usaco08nov]奶牛混合起来mixedupcows（dp）
传送门 f[i][S]表示当前集合为S，最后一个数为i的最优解f[i][S]+=f[j][S-i](j,i∈S&&j!=i&&abs(a[i]-a[j])>k) ——代码1#include<cstdio>2#include<iostream>3#defineLLlonglong45i 查看详情
vijos1055奶牛浴场
Description求一个不覆盖指定点的最大子矩阵,(n,mleqslant3 imes10^5,Sleqslant5 imes10^3).Sol没有名字的算法都叫xjblg算法?枚举每个点成为极大子矩阵边界的情况,然后维护上下边界.还有一种情况就是左右边界是矩阵两边的情况,需要预处理一... 查看详情
[luogup2858][usaco06feb]奶牛零食treatsforthecows（dp）
传送门 f[i][j][k]表示左右两段取到i....j时，取k次的最优解可以优化k其实等于n-j+i则f[i][j]=max(f[i+1][j]+a[i]*(n-j+i),f[i][j-1]+a[j]*(n-j+i))边界f[i][i]=a[i]*n递推顺序不好求，所以选择记忆化搜索。 ——代码1#include<cstdio>2#incl 查看详情
[luogup3052][usaco12mar]摩天大楼里的奶牛cowsinaskyscraper（dp）
传送门 输出被阉割了。只输出最少分的组数即可。f数组为结构体f[S].cnt表示集合S最少的分组数f[S].v 表示集合S最少分组数下当前组所用的最少容量f[S]=min(f[S],f[S-i]+a[i])(i∈S)运算重载一下即可。 ——代码1#include&l... 查看详情
luogup2925干草出售0-1背包问题(代码片段)
LuoguP2925干草出售一、题目二、参考代码2.1二维dp2.2一维dp一、题目农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车... 查看详情
luogup2925干草出售0-1背包问题(代码片段)
LuoguP2925干草出售一、题目二、参考代码2.1二维dp2.2一维dp一、题目农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车... 查看详情
luogup2925干草出售0-1背包问题(代码片段)
LuoguP2925干草出售一、题目二、参考代码2.1二维dp2.2一维dp一、题目农民john面临一个很可怕的事实，因为防范失措他存储的所有稻草给澳大利亚蟑螂吃光了，他将面临没有稻草喂养奶牛的局面。在奶牛断粮之前，john拉着他的马车... 查看详情
luogup2345奶牛集会
二次联通门: luoguP2345奶牛集会 /*luoguP2345奶牛集会权值线段树以坐标为下标，坐标为值建立线段树对奶牛按听力由小到大排序对于要查的牛每次第i次放入奶牛起作用的v就是vi； 每次ans+=（xi*sum-sumxl）*vi+（... 查看详情
[luogup1005]矩阵取数游戏（dp+高精度）
传送门 和奶牛那个题很像，每一行状态互不影响，也就是求n遍DP不过高精度非常恶心，第一次写，调了我一上午。 ——代码1#include<cstdio>2#include<cstring>3#include<iostream>45structBig_int6{7ints[35],idx;8Big_int()9{10i... 查看详情
luogup2345奶牛集会
题目背景MooFest,2004Open题目描述约翰的N头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i头奶牛的坐标为Xi，没... 查看详情