首页 > 代码库 > Noi2007 货币兑换
Noi2007 货币兑换
我是萌萌的传送门
小半个上午+一下午都给了这题了QAQ……
都知道是斜率优化，问题是我看这题根本就是一个人一个式子啊(╯‵□′)╯︵┻━┻
算了，把我的过程列出来吧……
令$f[i]$表示第i天结束时强制卖出所有金券最多能得到的软妹币数量，枚举上一次买入金券的时间，就有
\begin{equation}f[i]=\max_{j=1}^{i-1}\{A_i x+B_i y\}\end{equation}
(这里没有写隐含条件$f[i]\ge f[i-1]$，记得更新完所有决策之后对下一个$f$取一下$\max$即可。)
其中$x,y$分别表示用f[j]的软妹币能买到的A券和B券的数量，手动解一个二元一次方程组之后可以得到转移方程
\begin{equation}f[i]=\max_{j=1}^{i-1}\{\frac{(A_iR_j+B_i)f[j]}{A_jR_j+B_j}\}\end{equation}
令$g[i]=\frac{f[i]}{A_iR_i+B_i}$，转移方程变为
\begin{equation}f[i]=\max_{j=1}^{i-1}\{(A_iR_j+B_i)g[j]\}\end{equation}
考虑用哪些决策更新$f[i]$会比其他决策更优，设决策$k$比$j$更优，那么有
\begin{equation}(A_iR_k+B_i)g[k]>(A_iR_j+B_i)g[j]\end{equation}
移项得
\begin{equation}A_i(R_kg[k]-R_jg[j])>B_i(g[j]-g[k])\end{equation}
假设$g[k]>g[j]$，左右同除$A_i(g[j]-g[k])$(显然这个东西一定是负数)，得
\begin{equation}\frac{R_kg[k]-R_jg[j]}{g[j]-g[k]}<\frac{B_i}{A_i}\end{equation}
令$x_i=g[i],y_i=-R_ig[i]$，然后就是标准的斜率$<$一个只与$i$有关的常量的式子了。因为之前已经规定$x_k>x_j$，画个图可以发现最优决策点一定处在下凸壳上，平衡树维护凸壳或者CDQ分治即可。鉴于没写过平衡树维护凸壳(主要是不太会写用一条直线去切凸壳的操作……)，就用CDQ分治好了。
每层分治时先递归左边计算出左边的所有$f$值，然后用左边的凸壳更新右边的所有$f$，之后递归右边计算出右边的所有$f$值，这时区间内所有点的坐标都已知了，线性归并左右两个凸壳即可。为了保证复杂度需要先归并排序预处理所有点对应询问的斜率，用左边更新右边时离线扫描凸壳并更新决策。
代码里的$t[][]$是预处理时每层按斜率排序之后的编号，$a[]$是用来存凸壳的，$s$是算凸壳的时候用到的栈。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 const int maxn=100010; 7 const long double eps=1e-7; 8 void mergesort(int,int,int); 9 int CDQ(int,int,int); 10 long double getk(int,int); 11 long double w(int,int); 12 long double A[maxn],B[maxn],R[maxn],f[maxn],x[maxn],y[maxn],k[maxn]; 13 double tmp; 14 int n,t[20][maxn],a[maxn],s[maxn]; 15 int main(){ 16 freopen("cash.in","r",stdin); 17 freopen("cash.out","w",stdout); 18 scanf("%d%lf",&n,&tmp); 19 f[1]=tmp; 20 for(int i=1;i<=n;i++){ 21 scanf("%lf",&tmp); 22 A[i]=tmp; 23 scanf("%lf",&tmp); 24 B[i]=tmp; 25 scanf("%lf",&tmp); 26 R[i]=tmp; 27 k[i]=B[i]/A[i]; 28 } 29 mergesort(1,n,0); 30 CDQ(1,n,1); 31 printf("%.3lf",(double)f[n]); 32 return 0; 33 } 34 void mergesort(int l,int r,int d){ 35 if(l>=r){ 36 t[d][l]=l; 37 return; 38 } 39 int mid=(l+r)>>1; 40 mergesort(l,mid,d+1); 41 mergesort(mid+1,r,d+1); 42 int i=l,j=mid+1,p=l; 43 while(i<=mid&&j<=r){ 44 if(k[t[d+1][i]]<=k[t[d+1][j]])t[d][p++]=t[d+1][i++]; 45 else t[d][p++]=t[d+1][j++]; 46 } 47 while(i<=mid)t[d][p++]=t[d+1][i++]; 48 while(j<=r)t[d][p++]=t[d+1][j++]; 49 } 50 int CDQ(int l,int r,int d){ 51 if(l>=r){ 52 a[l]=l; 53 x[l]=f[l]/(A[l]*R[l]+B[l]); 54 y[l]=-R[l]*x[l]; 55 f[l+1]=max(f[l+1],f[l]); 56 return 1; 57 } 58 int mid=(l+r)>>1,cntl=CDQ(l,mid,d+1),i=l,j=mid+1; 59 while(i<l+cntl-1&&j<=r){ 60 if(getk(a[i],a[i+1])-eps<k[t[d][j]])i++; 61 else{ 62 f[t[d][j]]=max(f[t[d][j]],w(a[i],t[d][j])); 63 j++; 64 } 65 } 66 while(j<=r){ 67 f[t[d][j]]=max(f[t[d][j]],w(a[i],t[d][j])); 68 j++; 69 } 70 int cntr=CDQ(mid+1,r,d+1),cnt=l-1; 71 i=l;j=mid+1; 72 while(i<l+cntl&&j<=mid+cntr){ 73 if(fabs(x[a[i]]-x[a[j]])<=eps){ 74 x[a[i]]=min(x[a[i]],x[a[j]]); 75 j++; 76 } 77 else if(x[a[i]]<x[a[j]]){ 78 while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[i]))cnt--; 79 s[++cnt]=a[i++]; 80 } 81 else{ 82 while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[j]))cnt--; 83 s[++cnt]=a[j++]; 84 } 85 } 86 while(i<l+cntl){ 87 while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[i]))cnt--; 88 s[++cnt]=a[i++]; 89 } 90 while(j<=mid+cntr){ 91 while(cnt>l&&getk(s[cnt-1],s[cnt])+eps>getk(s[cnt],a[j]))cnt--; 92 s[++cnt]=a[j++]; 93 } 94 copy(s+l,s+r+1,a+l); 95 return cnt-l+1; 96 } 97 inline long double getk(int i,int j){return (y[i]-y[j])/(x[i]-x[j]);} 98 inline long double w(int j,int i){return f[j]*(A[i]*R[j]+B[i])/(A[j]*R[j]+B[j]);}
写了一下午，除去一些脑残错误，最重要的是推式子的时候两边同乘/除的数的正负性一！定！要！确！定！……
好不容易把CDQ分治全改对了，发现还是会WA，然后发现自己推的式子里两边同除了一个可能为正也可能为负的东西，然后斜率式子的不等号就不确定了……重新推了一个式子才过的，多谢后世人，戒之慎勿忘……
Noi2007 货币兑换