题解 P2900 【[USACO08MAR]Land Acquisition G】

在这个地方同时讲一下斜率优化,大佬们就请无视了吧。

注意:一定要看清横纵坐标是什么!!!!!!!!

很容易看出这是一道暴力题,然后我们超时了。

我们想一想该怎么做。

首先容易想到的一个优化便是:如果一片土地的长与宽都少于其他的一片土地,就把他排除。

所以我们先用长(设为x)排个序,假设从小到大吧,那么宽(设为y)会怎样呢?剔除不需要的后发现y单调递减。

比如:一开始拍完序后情况是这样的(横坐标x,纵坐标y),
题解 P2900 【[USACO08MAR]Land Acquisition G】
我们发现买了 3 ∗ 10 3*10 3∗10 的土地,就能把 1 ∗ 10 1*10 1∗10 的土地和 2 ∗ 8 2*8 2∗8 的土地包括了,所以前两个点就可以去掉,

情况就变成如下:(横坐标x,纵坐标y)
题解 P2900 【[USACO08MAR]Land Acquisition G】
最后你会发现,保证合法的情况是单调递减的(这对后面考虑有点影响)。

剔除无用的数据之后,我们可以想到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[] 。

题解 P2900 【[USACO08MAR]Land Acquisition G】
我们刚刚忙了那么多,就是为了维护这个单调递增的斜率绝对值。

专业术语好像叫做维护凸包。

我们就这样及时丢掉没用的点,节约了时间。复杂度 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;
}
上一篇:[洛谷2900][USACO08MAR]土地征用Land Acquisition(斜率优化dp)


下一篇:Land Rover Aurora 2014 airbag repair using CG100 Pro III