隐藏
「NOI2007」货币兑换 - 动态规划+斜率优化+CDQ分治维护凸包 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「NOI2007」货币兑换 - 动态规划+斜率优化+CDQ分治维护凸包

题目大意


题目分析

显然这道题是一道1D/1D动态规划的问题,我们可以尝试写出方程。
显然,我们如果在每一天要买或卖,不会部分操作,肯定要么全部买要么全部卖。

状态转移

那么设第$i$天没有A、B券,可以买入的A、B券分别有$X_i$和$Y_i$个,能够兑换的人民币为$f_i$。
显然有:

移项得:

状态转移方程是:

这个两项$i,j$相乘的形式是不是很像斜率优化,但是这里有两个因此我们还需要移项:

$y=kx+b$这不就是直线方程的形式了?
我们将$X_i$、$Y_i$看做一个点的横纵坐标,要使$f_i$最大,而$B_i$是大于0的常量,所以使得截距$\frac{f_i}{B_i}$最大即可。(是不是很神奇,所以斜率优化的$f$并不一定是纵坐标$y$,要灵活转化)

斜率优化

考虑这样的点可能存在于什么地方。

如图,我们可以发现,对于相同的斜率的直线,直线上的点在上凸壳时可以使截距最大。

那么斜率优化只需要维护一个上凸壳即可。
然而这题就非常坑爹了,平时我们用单调队列维护的斜率优化满足两个性质,插入的点的$x$值单增,并且询问的斜率$k$也是单调的,然而本题的$x$与$k$都不满足这个性质。

维护凸包

既然乱插点,我们就可以用平衡树维护凸包找寻前驱后继,但此处不介绍这种方法,因为编程复杂度非常的高而且难以调试。

既然无序,那么我们就让他强行有序,我们需要维护这些信息的有序性:

  • 斜率$k$
  • 由横坐标$x$、纵坐标$y$构成的水平序
  • 动规阶段$1\rightarrow n$

维护三维偏序,想到了什么?没错,我们搬出降维打击的终极武器:CDQ分治。

使用CDQ分治动规的阶段,事先对$k$排序(注意因为是右上凸包,因此斜率按照从大到小排序)。

按照以前说的方法,我们依次执行以下步骤:

具体步骤

1.若Left==Right,说明到达单位区间,那么我们即可计算出$f$值,同时计算出$x$、$y$的值

1
2
3
4
5
6
if(Left==Right) {
f[Left]=max(f[Left],f[Left-1]);
p[Left].y=f[Left]/(p[Left].a*p[Left].rate+p[Left].b);
p[Left].x=p[Left].y*p[Left].rate;
return;
}

2.按照阶段编号分为左右两个区间

1
2
3
4
5
6
int mid=(Left+Right)>>1;
int lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(p[i].id<=mid)tmp[lpos++]=p[i];
else tmp[rpos++]=p[i];
for(int i=Left; i<=Right; i++)p[i]=tmp[i];

3.递归左子区间

1
CDQBinary(Left,mid);

4.处理右区间中的点由左区间的点转移得到的情况
首先我们需要使用单调队列求出左区间的上凸壳。

1
2
3
4
double Slope(int a,int b) {
if(dcmp(p[a].x-p[b].x)==0)return 1e17;
return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
1
2
3
4
5
deque<int>Q;
for(int i=Left; i<=mid; i++) { //求出左区间上凸壳
while(Q.size()>=2&&Slope(Q[Q.size()-2],Q.back())<Slope(Q.back(),i))Q.pop_back();
Q.push_back(i);
}

然后利用左区间的上凸壳更新右区间的$f$值。(最优决策一定在上凸壳,分治处理)

1
2
3
4
for(int i=mid+1; i<=Right; i++) {
while(Q.size()>=2&&Slope(Q.front(),Q[1])>p[i].k)Q.pop_front();
f[p[i].id]=max(f[p[i].id],p[Q.front()].x*p[i].a+p[Q.front()].y*p[i].b);
}

5.递归右区间

1
CDQBinary(mid+1,Right);

6.归并排序
这和以前的归并不太一样,以前的归并上去后左右区间的顺序是一样的,从而进行后续处理。
但是因为我们是通过的左区间的上凸壳更新右区间的答案,故左区间的顺序应该是水平序,而右区间的顺序应该是斜率$k$的顺序。
那么归并的时候我们应该归并成为水平序。

1
2
3
bool cmp(const Point& a,const Point& b) {
return a.x<b.x||(dcmp(a.x-b.x)==0&&a.y<b.y);
}
1
2
3
merge(p+Left,p+mid+1,p+mid+1,p+Right+1,tmp,cmp);
int tot=0;
for(int i=Left; i<=Right; i++)p[i]=tmp[tot++];

那么这个问题就解决了,CDQ分治是不是很有用啊~


代码

这道题有点卡精度,调不出来不要砸键盘,键盘很痛的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=100005;
struct Point {
double a,b,rate;
double x,y,k;
int id;
bool operator < (const Point& b) const {
return k>b.k;
}
} p[maxn],tmp[maxn];
const double eps=1e-8;
int dcmp(double x) {
if(fabs(x)<=eps)return 0;
if(x>eps)return 1;
return -1;
}
double f[maxn];
bool cmp(const Point& a,const Point& b) {
return a.x<b.x||(dcmp(a.x-b.x)==0&&a.y<b.y);
}
double Slope(int a,int b) {
if(dcmp(p[a].x-p[b].x)==0)return 1e17;
return (p[b].y-p[a].y)/(p[b].x-p[a].x);
}
void CDQBinary(int Left,int Right) {
if(Left==Right) {
f[Left]=max(f[Left],f[Left-1]);
p[Left].y=f[Left]/(p[Left].a*p[Left].rate+p[Left].b);
p[Left].x=p[Left].y*p[Left].rate;
return;
}
int mid=(Left+Right)>>1;
int lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(p[i].id<=mid)tmp[lpos++]=p[i];
else tmp[rpos++]=p[i];
for(int i=Left; i<=Right; i++)p[i]=tmp[i];
CDQBinary(Left,mid);
deque<int>Q;
for(int i=Left; i<=mid; i++) { //求出左区间上凸壳
while(Q.size()>=2&&Slope(Q[Q.size()-2],Q.back())<Slope(Q.back(),i))Q.pop_back();
Q.push_back(i);
}
for(int i=mid+1; i<=Right; i++) {
while(Q.size()>=2&&Slope(Q.front(),Q[1])>p[i].k)Q.pop_front();
f[p[i].id]=max(f[p[i].id],p[Q.front()].x*p[i].a+p[Q.front()].y*p[i].b);
}
CDQBinary(mid+1,Right);
merge(p+Left,p+mid+1,p+mid+1,p+Right+1,tmp,cmp);
int tot=0;
for(int i=Left; i<=Right; i++)p[i]=tmp[tot++];
}
int n;
int main() {
ios::sync_with_stdio(false);
cin>>n>>f[0];
for(int i=1; i<=n; i++) {
cin>>p[i].a>>p[i].b>>p[i].rate;
p[i].k=-p[i].a/p[i].b;
p[i].id=i;
}
sort(p+1,p+n+1); //斜率序
CDQBinary(1,n);
printf("%0.3lf\n",f[n]);
return 0;
}

姥爷们赏瓶冰阔落吧~