[DP记录]P4027 [NOI2007]货币兑换

command_block · 2020-02-02 18:29:13 · 个人记录

广告 : 一些常用的数据结构维护手法

这就是CDQ神当年的论文题。

第一眼看上去根本联想不到CDQ,我们先简化一下决策。

首先容易猜到的是 : 一旦花钱就花完,一旦卖出就卖完,不会留。

理解 : 由于按比例消费,我们可以把钱拆成几份,每份单独决策,因为是等价的,所以决策必然相同。

现在就是这么样一个过程:

Begin   买----卖    买-----------卖 买----卖 ...  End

这就是个经典的分段问题了,考虑DP。

设F[i]表示第i天最多能够得到多少钱。

边界F[1]=S;

转移是F[j]=\max(F[j-1],\max\limits_{i=0}^{j-1}F[i]*c(i,j))

其中c(i,j)是在第i天买入,第j天卖出可取得的利润比例。

求解一下,设第i天能换得x_i个A卷,y_i个B卷,则有:

\begin{cases}x_i:y_i=R_i:1\\x_i·A_i+y_i·B_i=F[i]\end{cases}

解得\large\begin{cases}x_i=\frac{F[i]·R_i}{A_i+R_i·B_i}\\y_i=\frac{F[i]}{A_i+R_i·B_i}\end{cases}

然后再计算在第j天把它们全部卖出所得到的RMB:

c(i,j)=x_i·A_j+y_i·B_j

这不是个一元一次式,但是没有常系数,考虑提取B_j

=B_j(x_i·\frac{A_j}{B_j}+y_i)

后面就是个一元一次式了,我们把x_i看做斜率,y_i看做截距,构造直线y=x_i·x+y_i

每次我们求值的时候,相当于拿\frac{A_j}{B_j}当做x代入求值,并在众多直线(决策)中找到最大值。

您可以康康 DP的决策单调性优化总结中的“斜率优化”部分。

现在我们要维护这样的一个数据结构:

Q$ : 询问$x=c$时,所有直线的函数值$\max

我们惊喜的发现,这里插入直线的斜率并不单调,询问x坐标也不单调……

一种做法是 : Splay维护凸壳,虽然理论复杂度O(nlogn)十分优秀,但是很难写,常数也较大。

我们考虑CDQ分治,就能把这玩意变成静态了。

观察静态的问题 :

我们可以对直线按照斜率排序,然后就可以使用单调栈构造凸壳。

查询不需要仍然在凸壳上二分,直接对询问的x排序,就能依靠单调性求解。

我们惊喜的发现,静态的问题我们会做!除去排序,复杂度O(n)。

不过注意的是,这是个DP问题,我们后面的修改要依赖前面的询问答案。

所以需要采用中序遍历来分治,而问题又在于,我们如果要快速获得排序结果,则必须采用后序遍历进行归并。

一种办法是保存每一层归并的结果,但是会使内存达到O(n\log n),劣于平衡树。

我们可以将询问在外面预先排好序,然后按照时间顺序再拆分给子问题。这样就能得到有序的询问了。

归并技巧进阶

在CDQ分治中,可以批量回答询问,所以可以对询问进行预处理来达到复杂度更低的目的。

比如说这题,就可以归并得到询问的排序,从而达到均摊O(m)的静态问题解法。

在二进制分组中,虽然对内层数据结构的要求类似,但是无法对讯问进行预处理。

总的复杂度是O(nlogn),感觉当年写O(nlog^2n)不一定卡的过……

在某个地方乱丢了个for循环,结果TLE了半天,服了……

#include<algorithm>
#include<cstdio>
#define db double
#define MaxN 105000
using namespace std;
struct Line{db k,b,hk;}
b[MaxN],q[MaxN],L;
db inter(Line &A,Line &B){
  return A.k==B.k ? (A.b<B.b ? 1e12 : -1e12)
     : (B.b-A.b)/(A.k-B.k);
}
int tot;
void add(){
  while(tot>1&&inter(L,q[tot])<q[tot].hk)tot--;
  q[++tot]=L;q[tot].hk=inter(L,q[tot-1]); 
}
db F[MaxN],A[MaxN],B[MaxN],R[MaxN];
struct Data
{db x;int p;}c[MaxN],sr[MaxN];
void solve(int l,int r)
{
  if (l==r){
    F[l]=max(F[l],F[l-1]);
    b[l].b=F[l]/(B[l]+R[l]*A[l]);
    b[l].k=b[l].b*R[l];
    return ;
  }int mid=(l+r)>>1,tl=l-1,tr=0;
  for (int i=l;i<=r;i++)
    if (c[i].p<=mid)c[++tl]=c[i];
    else sr[++tr]=c[i];
  for (int i=mid+1;i<=r;i++)c[i]=sr[i-mid];
  solve(l,mid);tot=0;
  for (int i=l;i<=mid;i++){L=b[i];add();}
  for (int i=mid+1,p=1;i<=r;i++){
    while(p<tot&&q[p+1].hk<c[i].x)p++;
    int tp=c[i].p;
    F[tp]=max(F[tp],A[tp]*q[p].k+B[tp]*q[p].b);
  }solve(mid+1,r);
  tr=mid+1;tot=0;
  for (int i=l;i<=mid;i++){
    while(tr<=r&&b[tr].k<b[i].k)
      q[++tot]=b[tr++];
    q[++tot]=b[i];
  }while(tr<=r)q[++tot]=b[tr++];
  for (int i=l;i<=r;i++)b[i]=q[i-l+1];
}
bool cmp(const Data &A,const Data &B)
{return A.x<B.x;}
int n;
int main()
{
  scanf("%d%lf",&n,&F[1]);
  for (int i=1;i<=n;i++){
    scanf("%lf%lf%lf",&A[i],&B[i],&R[i]);
    c[i]=(Data){A[i]/B[i],i};
  }sort(c+1,c+n+1,cmp);
  solve(1,n);
  printf("%.6lf",F[n]);
  return 0;
}