程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj1492--斜率優化DP+cdq分治

bzoj1492--斜率優化DP+cdq分治

編輯:關於C++

bzoj1492--斜率優化DP+cdq分治。本站提示廣大學習愛好者:(bzoj1492--斜率優化DP+cdq分治)文章只能為提供參考,不一定能成為您想要的結果。以下是bzoj1492--斜率優化DP+cdq分治正文


顯然在某一天要麼花完一切錢,要麼不花錢。

所以首先想到O(n^2)DP:

f[i]=max{f[i-1],(f[j]*r[j]*a[i]+f[j]*b[i])/(a[j]*r[j]+b[j])},j<i

其中f[j]*r[j]/(a[j]*r[j]+b[j])是第j天最多能買多少A券,B相似。

假設我們曾經找到了最優的j,那麼有f[i]=(f[j]*r[j]*a[i]+f[j]*b[i])/(a[j]*r[j]+b[j])

令x[j]=f[j]*r[j]/(a[j]*r[j]+b[j]),y[j]=f[j]/(a[j]*r[j]+b[j])

那麼有f[i]=x[j]*a[i]+y[j]*b[i]

        y[j]=(-a[i]/b[i])*x[j]+f[i]/b[i]
這是一條斜率為-a[i]/b[i]的直線。

由於b[i]不變,而我們要最大化f[i],所以如今我們可以將問題轉化為從一些點中選出一個點,使經過這點的已知斜率的直線的截距最大。

但由於斜率和坐標都是無序的,我們用splay維護一個上凸殼,在求f[i]時從上凸殼中選出一個點j,使j點左右兩邊的斜率剛好將-a[i]/b[i]夾住,那麼i就從j轉移。

但這題還有更神奇的cdq分治做法。

我們可以想想,為什麼斜率和坐標都是無序的呢?由於我們從1~n順次求解。那能否依照斜率排序後逐個求解呢?答案是能。

處置區間[l,r]時先將[l,mid]建成一個上凸殼,然後將[mid+1,r]按斜率排序並更新就可以了。

時間復雜度O(n*logn)

 

代碼:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 #define N 100001
 8 #define Eps 1e-9
 9 #define INF 0x3f3f3f3f3f3f3f3f
10 struct Node{
11   double x,y,A,B,r,k;
12   int Id;
13 }a[N],t[N];
14 double f[N];
15 int i,j,St[N],Top,n,m;
16 inline bool Cmp(Node a,Node b){return a.k<b.k;}
17 inline double _Max(double x,double y){return x<y?y:x;}
18 inline double Slop(int x,int y){
19   if(!y)return -1e20;
20   if(fabs(a[x].x-a[y].x)<Eps)return 1e20;
21   return (a[x].y-a[y].y)/(a[x].x-a[y].x);
22 }
23 inline void Solve(int l,int r){
24   if(l==r){
25     f[l]=_Max(f[l],f[l-1]);
26     a[l].y=f[l]/(a[l].A*a[l].r+a[l].B);
27     a[l].x=a[l].y*a[l].r;
28     return;
29   }
30   int Mid=l+r>>1;
31   int l1=l,l2=Mid+1;
32   for(int i=l;i<=r;i++)
33     if(a[i].Id<=Mid)t[l1++]=a[i];else t[l2++]=a[i];
34   for(int i=l;i<=r;i++)a[i]=t[i];
35   Solve(l,Mid);
36   Top=0;
37   for(int i=l;i<=Mid;i++){
38     while(Top>1&&Slop(St[Top-1],i)+Eps>Slop(St[Top-1],St[Top]))Top--;
39     St[++Top]=i;
40   }
41   int j=1;
42   St[++Top]=0;
43   for(int i=r;i>Mid;i--){
44     while(j<Top&&a[i].k<Slop(St[j],St[j+1])+Eps)j++;
45     f[a[i].Id]=_Max(f[a[i].Id],a[St[j]].x*a[i].A+a[St[j]].y*a[i].B);
46   }
47   Solve(Mid+1,r);
48   l1=l,l2=Mid+1;
49   for(int i=l;i<=r;i++)
50     if(l1>Mid)t[i]=a[l2++];else
51       if(l2>r)t[i]=a[l1++];else
52     if(a[l1].x<a[l2].x||(fabs(a[l1].x-a[l2].x)<Eps&&a[l1].y<a[l2].y))t[i]=a[l1++];else t[i]=a[l2++];
53   for(int i=l;i<=r;i++)a[i]=t[i];
54 }
55 int main()
56 {
57   scanf("%d%lf",&n,&f[0]);
58   for(i=1;i<=n;i++){
59     scanf("%lf%lf%lf",&a[i].A,&a[i].B,&a[i].r);
60     a[i].Id=i;a[i].k=-a[i].A/a[i].B;
61   }
62   sort(a+1,a+n+1,Cmp);
63   Solve(1,n);
64   printf("%.3lf",f[n]);
65   return 0;
66 }
bzoj1492

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved