在这个地方同时讲一下斜率优化,大佬们就请无视了吧。
注意:一定要看清横纵坐标是什么!!!!!!!!
很容易看出这是一道暴力题,然后我们超时了。
我们想一想该怎么做。
首先容易想到的一个优化便是:如果一片土地的长与宽都少于其他的一片土地,就把他排除。
所以我们先用长(设为x)排个序,假设从小到大吧,那么宽(设为y)会怎样呢?剔除不需要的后发现y单调递减。
比如:一开始拍完序后情况是这样的(横坐标x,纵坐标y),
我们发现买了
3
∗
10
3*10
3∗10 的土地,就能把
1
∗
10
1*10
1∗10 的土地和
2
∗
8
2*8
2∗8 的土地包括了,所以前两个点就可以去掉,
情况就变成如下:(横坐标x,纵坐标y)
最后你会发现,保证合法的情况是单调递减的(这对后面考虑有点影响)。
剔除无用的数据之后,我们可以想到dp的思维。
我们来考虑最后选取的一个土地组合。
转移方程 f [ i ] = f [ j ] + x [ i ] ∗ y [ j + 1 ] f[i]=f[j]+x[i]*y[j+1] f[i]=f[j]+x[i]∗y[j+1] 注意 f [ j ] f[j] f[j]已经包括了 x [ j ] ∗ y [ j ] x[j]*y[j] x[j]∗y[j],所以要乘 y [ j + 1 ] y[j+1] y[j+1]。
转移方程 f [ i ] = f [ j ] + x [ i ] ∗ y [ j + 1 ] f[i]=f[j]+x[i]*y[j+1] f[i]=f[j]+x[i]∗y[j+1],我们假设i由j和k转移过来,
那么k比较优的要求便是:
f [ j ] + x [ i ] ∗ y [ j + 1 ] > f [ k ] + x [ i ] ∗ y [ k + 1 ] f[j]+x[i]*y[j+1] > f[k]+x[i]*y[k+1] f[j]+x[i]∗y[j+1]>f[k]+x[i]∗y[k+1]
最后变形为 ( f [ j ] − f [ k ] ) / ( y [ j + 1 ] − y [ k + 1 ] ) < − x [ i ] (f[j]-f[k])/(y[j+1]-y[k+1])<-x[i] (f[j]−f[k])/(y[j+1]−y[k+1])<−x[i],
发现左边同i无关,即可考虑乱搞一下了。
我们把这些点仍进一个双端队列里(具体为啥下面会讲)。
所以说这个式子又有什么卵用呢?
画几个图分析一下。
假设一个中间步骤,现在情况是这个样的。
注意:此时x轴为y(即宽度),y轴为f(即dp值),跟前面不一样
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-D5hFXhRg-1607167360784)(https://www.icode9.com/i/i/?n=17&i=blog/1113547/201802/1113547-20180209163248310-421036150.png)]
我们先从队首开始看。
队首的元素,取出q1和q2,此时q1,q2就相当于j,k两个转移点。
如果满足上述条件,也就是 ( f [ q 1 ] − f [ q 2 ] ) / ( y [ q 1 + 1 ] − y [ q 2 + 1 ] ) < − x [ i ] (f[q1]-f[q2])/(y[q1+1]-y[q2+1])<-x[i] (f[q1]−f[q2])/(y[q1+1]−y[q2+1])<−x[i]时,由我们前面得到的结论,
可以知道用q1转移不如用q2转移了,然后就可以把队首元素残忍地抛弃,让下一个来当队首。
下一个当然也可能不如再下一个,所以用一个while处理队首的元素。
我们再考虑队尾的情况。
设 s ( a , b ) = ( f [ q 1 ] − f [ q 2 ] ) / ( y [ q 1 + 1 ] − y [ q 2 + 1 ] s(a,b)=(f[q1]-f[q2])/(y[q1+1]-y[q2+1] s(a,b)=(f[q1]−f[q2])/(y[q1+1]−y[q2+1]。
所以队尾优化应该借鉴一下开头的写法。
然后你就没有什么思路了。
我们来研究一下 s ( j , k ) s(j,k) s(j,k) 和 s ( k , i ) s(k,i) s(k,i) 的情况。
若 s ( j , k ) < s ( k , i ) s(j,k)<s(k,i) s(j,k)<s(k,i):
①若 s ( j , k ) < − x [ i ] s(j,k)<-x[i] s(j,k)<−x[i] ,那么k比j优,但由于 s ( j , k ) < s ( k , i ) s(j,k)<s(k,i) s(j,k)<s(k,i) 我们知道 s ( k , i ) < − x [ i ] s(k,i)<-x[i] s(k,i)<−x[i] ,从而推出由k转移不如由i自己转移。
②若 s ( j , k ) > = x [ i ] s(j,k)>=x[i] s(j,k)>=x[i] ,那么k就不必j优,k也是没用的了。
所以,当 s ( j , k ) < s ( k , i ) s(j,k)<s(k,i) s(j,k)<s(k,i) 时,我们就可以把k残忍地抛弃了。
具体表现就是满足条件就扔掉队尾,让队尾前一个当队尾,跟前面一样用个 w h i l e while while。
两端排除没用的点使这种效率非常高。
我们再来看一下这个式子: ( f [ j ] − f [ k ] ) / ( y [ j + 1 ] − y [ k + 1 ] ) < − x [ i ] (f[j]-f[k])/(y[j+1]-y[k+1])<-x[i] (f[j]−f[k])/(y[j+1]−y[k+1])<−x[i] ,
因为 x [ i ] x[i] x[i] 我们排过序,是从左往右单调递增的,
我们再给他变个行 ( f [ j ] − f [ k ] ) / ( y [ k + 1 ] − y [ j + 1 ] ) > x [ i ] (f[j]-f[k])/(y[k+1]-y[j+1])>x[i] (f[j]−f[k])/(y[k+1]−y[j+1])>x[i] ,
由于 x [ i ] x[i] x[i] 在递增,所以我们看出斜率的绝对值在越变越大。
最后大概图是这个样的, x x x 轴代表 y y y , y y y 轴代表 f [ ] f[] f[] 。
我们刚刚忙了那么多,就是为了维护这个单调递增的斜率绝对值。
专业术语好像叫做维护凸包。
我们就这样及时丢掉没用的点,节约了时间。复杂度 O ( n ) O(n) O(n) 。
好了说了这么多,上蒟蒻的代码吧。
不要忘了long long orz。
代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
const int maxn=50010;
struct node{
ll x,y;
}a[maxn];
bool cmp(const node &aa,const node &bb){
return aa.x<bb.x;
}
ll n,cnt;
ll f[maxn];
ll q[maxn],head,tail;
double k(ll aa,ll bb){
return ((double)(f[aa]-f[bb]))/((double)(a[aa+1].y-a[bb+1].y));
}
int main(){
scanf("%lld",&n);
for (int i=1;i<=n;++i){
scanf("%lld%lld",&a[i].x,&a[i].y);
}
sort(a+1,a+1+n,cmp);
for (int i=1;i<=n;++i){
while (cnt&&a[i].y>=a[cnt].y) --cnt;
a[++cnt]=a[i];
}
n=cnt; head=tail=1;
for (int i=1;i<=n;++i){
while (head<tail&&k(q[head],q[head+1])>=-a[i].x) head++;
f[i]=f[q[head]]+a[i].x*a[q[head]+1].y;
while (head<tail&&k(q[tail-1],q[tail])<k(q[tail],i)) tail--;
q[++tail]=i;
}
printf("%lld",f[n]);
return 0;
}