bzoj 1597 [Usaco2008 Mar]土地购买——斜率优化dp

时间:2023-03-08 17:36:51
bzoj 1597 [Usaco2008 Mar]土地购买——斜率优化dp

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1597

又一道斜率优化dp。负数让我混乱。不过仔细想想还是好的。

  还可以方便地把那个负号放到x上。只要改一下slope里的一个负号,就变成正常舒服的递增了。

这道题的要点其实是一开始h=0。不能h=1。这样就能把dp[0]纳入考虑。这是需要的。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=5e4+;
int n,top,h,t,q[N];
ll dp[N];
struct Node{
ll a,b;double k;
}r[N];
bool cmp(Node u,Node v){return u.a<v.a;}
double slope(int u,int v)
{
return (dp[u]-dp[v])/(r[u+].b-r[v+].b);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%lld%lld",&r[i].a,&r[i].b);
sort(r+,r+n+,cmp);
for(int i=;i<=n;i++)
{
while(top&&r[i].b>=r[top].b)top--;
r[++top].a=r[i].a;r[top].b=r[i].b;
}
h=;t=;
for(int i=;i<=top;i++)
{
while(h<t&&slope(q[h+],q[h])>=-r[i].a)h++;
dp[i]=dp[q[h]]+r[i].a*r[q[h]+].b;
while(h<t&&slope(i,q[t-])>=slope(q[t],q[t-]))t--;
q[++t]=i;
// printf("h:a=%d b=%d t:a=%d b=%d\n",r[q[h]].a,r[q[h]].b,r[q[t]].a,r[q[t]].b);
// for(int i=1;i<=top;i++)printf("dp[%d]=%.0lf\n",i,dp[i]);
}
printf("%lld",dp[top]);
return ;
}