斜率优化 – 徐亦轲的博客

// <1597.cpp> - 07/19/16 20:00:09
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
 #include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=50010;
const int INF=1e9;
struct land{
    int x,y;
    bool operator <(const land b) const{return x==b.x?y<b.y:x<b.x;}
}a[MAXN];
lol dp[MAXN];
#define k(u,v) double(dp[v-1]-dp[u-1])/(a[v].y-a[u].y)
int q[MAXN];
bool v[MAXN];
int main(){
    int n=gi();
    for(int i=1;i<=n;i++)a[i].x=gi(),a[i].y=gi();
    sort(a+1,a+n+1);
    int maxy=0;
    for(int i=n;i;i--)
        if(a[i].y>maxy)v[i]=1,maxy=max(maxy,a[i].y);
    int t=0;
    for(int i=1;i<=n;i++)if(v[i])a[++t]=a[i];
    n=t;
    int l=1,r=0;
    for(int i=1;i<=n;i++){
        while(l<r&&k(q[r-1],q[r])<=k(q[r],i))r--;
        q[++r]=i;
        while(l<r&&k(q[l],q[l+1])>=-a[i].x)l++;
        dp[i]=dp[q[l]-1]+1ll*a[i].x*a[q[l]].y;
    }
    printf("%lld",dp[n]);
    return 0;
}

// <1597.cpp> - 07/19/16 20:00:09

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=50010;

const int INF=1e9;

struct land{

int x,y;

bool operator <(const land b) const{return x==b.x?y<b.y:x<b.x;}

}a[MAXN];

lol dp[MAXN];

#define k(u,v) double(dp[v-1]-dp[u-1])/(a[v].y-a[u].y)

int q[MAXN];

bool v[MAXN];

int main(){

int n=gi();

for(int i=1;i<=n;i++)a[i].x=gi(),a[i].y=gi();

sort(a+1,a+n+1);

int maxy=0;

for(int i=n;i;i--)

if(a[i].y>maxy)v[i]=1,maxy=max(maxy,a[i].y);

int t=0;

for(int i=1;i<=n;i++)if(v[i])a[++t]=a[i];

n=t;

int l=1,r=0;

for(int i=1;i<=n;i++){

while(l<r&&k(q[r-1],q[r])<=k(q[r],i))r--;

q[++r]=i;

while(l<r&&k(q[l],q[l+1])>=-a[i].x)l++;

dp[i]=dp[q[l]-1]+1ll*a[i].x*a[q[l]].y;

}

printf("%lld",dp[n]);

return 0;

}

【BZOJ1096】【ZJOI2007】仓库建设

2016年6月30日2016年5月24日由徐亦轲

居然又是斜率优化。。总结出一些规律：凡是看起来sb的dp复杂度又不对的就是斜率优化。。当然一般是区间这样的问 … 阅读更多【BZOJ1096】【ZJOI2007】仓库建设

【BZOJ1911】【APIO2010】特别行动队

2016年6月30日2016年5月23日由徐亦轲

已经有感觉了诶。。一眼秒出是斜率优化因为修正战斗力是个二次函数并且开口向下，显然如果对于一个点x而言，l&l … 阅读更多【BZOJ1911】【APIO2010】特别行动队

【BZOJ1010】【HNOI2008】玩具装箱

2016年6月30日2016年5月14日由徐亦轲

AC数rank 3 感觉这题就是个**dp 想着赶快切了这道题的 $dp_i$表示以i为结尾的答案那么 $ … 阅读更多【BZOJ1010】【HNOI2008】玩具装箱

MasterJH5574 2019年3月10日 at 下午2:55 在日语(第二外国语)(3)笔记二……二股？
MLEAutoMaton 2019年2月18日 at 上午9:40 在友情链接申请友链！ http://mleautomaton.cf/
andyli 2019年2月1日 at 下午4:53 在友情链接申请友链
Happynewyear 2019年1月31日 at 下午2:53 在友情链接申请友链（虽然只有5篇博客，，，但以后不是了23333） https://githubhappynewyear.github.io/archives/
MasterJH5574 2018年12月5日 at 上午7:51 在日本語能力試験JLPT-N2游记可是我看不懂…… （可怜