[DP优化方法之斜率DP]

什么是斜率dp呢大概就把一些单调的分组问题从O(N^2)降到O(N) 具体的话我就不多说了看论文:

http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html

我自己也补充几句：

其实斜率dp有很多种打法有凸包有截距有直接比较斜率的因为我比较弱所以的话就学最弱智的比较斜率的听wph说截距很好理解

然后的话讲课的时候scy说什么要证单调性什么鬼的我在学的过程中好像没遇到就不管了虽然我很弱反正我能AC就行了

我们要知道的一点是我们要维护的是斜率递增还是递减的这很重要然后还要知道什么时候左边端点优什么时候右边端点优

我做这种题就是先枚举k<j<i 然后列出式子化简变成(.....) / (.....) < 或者 > x[i] 然后设两条斜率为g[i,j] g[j,k]

看看g[i,j]<g[j,k] 或者 g[i,j]>g[j,k]的情况看看有没有使j最不优的情况删掉j 然后描出这个队列里面合法的点就知道是单调递增还是递减了

其实我说的很乱别看好了直接上例题

[Usaco2008 Mar]土地购买

首先这一道题是求max的我们自然要办法处理一下先按x和y从小到大排序我们发现当i>j xi>xj yi>yj的时候 j是废的所以我们要重新搞一遍使得xi>xj yi<yj

这样就变成了x递增y递减的东西

然后斜率dp搞一下就好了注意如果没删去那些没用的直接搞会错的因为如果假设i>j i对于j来说j是废的那么的话F[i]就是继承F[j] 就是把i和j分成两组然后的话j又比j-1优(会有可能的好像我想了一下) 所以的话就继承了j的使原来不优但是的话j-1不优是因为Y[j-1+1]的影响了 (想一下我就因为这个wa了)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<climits>
#define Maxn 50010
using namespace std;
pair<double,double>pr[Maxn]; int N;
bool Cmp(const pair<double,double> &x,const pair<double,double> &y){if(x.first!=y.first) return x.first<y.first; return x.second<y.second;}
pair<double,double>S[Maxn]; int top=0; int Q[Maxn],head,tail; double F[Maxn];
inline double Slop(int j,int k){return (F[j]-F[k])/(S[k+1].second-S[j+1].second);}
int main()
{
  scanf("%d",&N); for(int i=1;i<=N;i++) scanf("%lf%lf",&pr[i].first,&pr[i].second);
  sort(pr+1,pr+N+1,Cmp); S[0]=make_pair(0,LLONG_MAX);
  for(int i=1;i<=N;i++){while(pr[i].second>=S[top].second) top--; S[++top]=pr[i];}
  head=1; tail=1; Q[head]=0;
  for(int i=1;i<=top;i++)
  {
    while(head<tail&&Slop(Q[head],Q[head+1])<=S[i].first) head++;
    F[i]=F[Q[head]]+S[i].first*S[Q[head]+1].second;
    while(head<tail&&Slop(Q[tail-1],Q[tail])>=Slop(Q[tail],i)) tail--; Q[++tail]=i;
  }
  return printf("%.0lf
",F[top]),0;
}
/*
4
100 1
15 15
20 5
1 100
1<=N<=50000
*/

View Code