链接
点击跳转
题解
斜率优化裸题
f
i
−
x
i
y
i
+
a
i
=
f
j
−
x
j
y
i
f_{i} -x_iy_i + a_i = f_j - x_jy_i
fi−xiyi+ai=fj−xjyi
令截距
b
=
f
i
−
x
i
y
i
+
a
i
b = f_{i} -x_iy_i + a_i
b=fi−xiyi+ai，
y
=
f
j
y = f_j
y=fj ，
x
=
x
j
x=x_j
x=xj，
k
=
y
i
k = y_i
k=yi
最大化截距，
k
>
0
k>0
k>0且单调减，那么维护上凸壳就好了
代码
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define maxe 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
#define de(x) cerr<<#x<<" = "<<x<<endl
using namespace std
;
using namespace __gnu_pbds
;
typedef long long ll
;
typedef pair
<int,int> pii
;
typedef pair
<ll
,ll
> pll
;
ll
read(ll x
=0)
{
ll c
, f(1);
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-0x30;
return f
*x
;
}
struct Rectangle
{ll x
, y
, a
;}r
[maxn
];
ll n
, f
[maxn
];
int main()
{
ll i
, j
, b
, ans
=0;
n
=read();
rep(i
,n
)r
[i
].x
=read(), r
[i
].y
=read(), r
[i
].a
=read();
sort(r
+1,r
+n
+1,[](Rectangle r1
, Rectangle r2
){return r1
.x
<r2
.x
;});
deque
<pll
> q
;
q
.emb(pll(0,0));
for(i
=1;i
<=n
;i
++)
{
ll k
=r
[i
].y
;
auto b
=[k
](pll p
){return p
.second
-k
*p
.first
;};
while(q
.size()>1 and b(q
[1])>b(q
[0]) )q
.pop_front();
f
[i
] = b(q
[0]) + r
[i
].x
*r
[i
].y
-r
[i
].a
;
ll xi
=r
[i
].x
, yi
=f
[i
];
auto vec
=[](pll p1
, pll p2
){return pll(p2
.first
-p1
.first
,p2
.second
-p1
.second
);};
auto cross
=[](pll v1
, pll v2
){return v1
.first
*v2
.second
-v1
.second
*v2
.first
;};
auto real_check
=[](pll p1
, pll p2
, pll p3
){return double(p3
.se
-p2
.se
)/(p3
.fi
-p2
.fi
)>double(p2
.se
-p1
.se
)/(p2
.fi
-p1
.fi
)+eps
;};
while(q
.size()>1 and real_check( q
.at(q
.size()-2), q
.back(), pll(xi
,yi
) ))
q
.pop_back();
q
.emb(pll(xi
,yi
));
ans
=max(ans
,f
[i
]);
}
std
::cout
<<ans
;
return 0;
}
斜率优化板子get！
deque
<pll
> q
;
q
.emb(pll(0,0));
for(i
=1;i
<=n
;i
++)
{
ll k
=r
[i
].y
;
auto b
=[k
](pll p
){return p
.second
-k
*p
.first
;};
while(q
.size()>1 and b(q
[1])>b(q
[0]) )q
.pop_front();
f
[i
] = b(q
[0]) + r
[i
].x
*r
[i
].y
-r
[i
].a
;
ll xi
=r
[i
].x
, yi
=f
[i
];
auto vec
=[](pll p1
, pll p2
){return pll(p2
.first
-p1
.first
,p2
.second
-p1
.second
);};
auto cross
=[](pll v1
, pll v2
){return v1
.first
*v2
.second
-v1
.second
*v2
.first
;};
auto real_check
=[](pll p1
, pll p2
, pll p3
){return double(p3
.se
-p2
.se
)/(p3
.fi
-p2
.fi
)>double(p2
.se
-p1
.se
)/(p2
.fi
-p1
.fi
)+eps
;};
while(q
.size()>1 and real_check( q
.at(q
.size()-2), q
.back(), pll(xi
,yi
) ))
q
.pop_back();
q
.emb(pll(xi
,yi
));
ans
=max(ans
,f
[i
]);
}
