[NOI2007] 货币兑换 解题报告

NOI 解题报告 dp

---

题目链接

题目大意

有 $A,B$ 两种金券，它们每天的价值都不同，在第 $i$ 天时分别为 $A_i,B_i$，你可以用手中的金券换取相应价值的钱，或用钱兑换相同价值的金券，但兑换到的两种金券的数量之比是一个定值，这个定值在第 $i$ 天为 $R_i$。
现给出 $n$ 天中两种金券的价值， $R$，以及你初始时拥有的资金 $S$，求 $n$ 天后你最多能有多少钱。
注：一定存在一种最优方案，满足：每次兑换金券花光所有的钱，每次换钱时花掉所有的金券。

解题思路

一眼dp题（大佬好像都是这样说的）。
先设个状态吧，
设 $f[i]$ 表示在第 $i$ 天卖掉所有的金券能获得的最多钱数，那我们只需要决定上一次买金券是在什么时候，转移方程如下：

$$f[i]=max \{ num_A*A_i+num_B*B_i \}$$
$num_A$ 和 $num_B$ 的值就取决与你上一次是在什么时候买的金券。

假设我们上一次是在第 $j$ 天买的金券，而上一次卖掉金券是在第 $k$ 天（$k\le j <i$），那么我们在第 $j$ 天拥有的资金就是 $f[k]$，可以得出式子：

$$num_A*A_j+num_B*B_j=f[k]$$
变个形
$$R_j*num_B*A_j+num_B*B_j=f[k]$$
移个项
$$num_B=\frac{f[k]}{R_j*A_j+B_j}$$
很容易看出来，$f[k]$ 越大越好，所以我们用个 $maxn$ 代替
$$num_B=\frac{maxn}{R_j*A_j+B_j}$$
现在，我们就可以得出完整的转移方程
$$f[i]=max \{ \frac{R_j*maxn}{R_j*A_j+B_j}*A_i+\frac{maxn}{R_j*A_j+B_j}*B_i \}$$

辣眼睛
一个 $n^2$ 算法就完成了，看下数据范围

对于 $100\%$ 的测试数据，满足 $1\le N\le 10^5$.....

手动再见

没办法，考虑优化吧。
再看眼式子

$$f[i]=max \{ num_A*A_i+num_B*B_i \}$$
与 $j$ 有关的和与 $i$ 有关的粘在了一起，单调队列是没法搞了，斜率优化吧。
把式子转化一下，先把 $max$ 扔掉，除个 $B_i$（这第一步我还是看了题解才知道的……）
$$\frac{f[i]}{B_i}=num_A*\frac{A_i}{B_i}+num_B$$
再移个项
$$num_B=-\frac{A_i}{B_i}*num_A+\frac{f[i]}{B_i}$$
搞定，妥妥的斜率优化，
但，
这里的 $num_A$ 和 $-\frac{A_i}{B_i}$ 都不是递增的，队列搞不了……
怎么办，不会做，

打开题解看一眼，平衡树，cdq，关上。

cdq没有思路，还是用平衡树吧，虽然写起来麻烦点（为了写这道题我又去敲了遍平衡树的板子，又调了一个小时……）

那现在思路就很明了了（可能吧），用平衡树维护一个上凸包，将凸包上的点按横坐标排序，然后每次找地方插入（或不插入），然后删除没用的点就行了，并在每一个点存下它与凸包上前一个点连接形成的直线的斜率 $tk$，更新状态时找到凸包上 $tk$ 比当前直线大的第一个点进行转移就行了（建议自己画个图理解一下）。

这道题貌似到这里就全部解完了，但实际上还有很多细节需要考虑，包括在插入、删除节点是要更新它的前驱和后缀的信息，以及花式卡精度……（数据里竟然出现了两个点的横坐标小数点后十几位都相同的情况……）。

最后这道题做下来前前后后花了可能有两天……

代码实现

#include<iostream>
#include<cstdlib>
#include<cstdio>
#define db double
using namespace std;
const int N=100000+7;
int n,q[N],rt,cnt;
db f[N],a[N],b[N],r[N],X[N],Y[N],K[N],maxn;
int lc[N],rc[N],p[N],pre[N],nxt[N];
db tk[N];
db read(){
    char c=getchar(); db f=1,x=0;
    while(c<'0'||c>'9'){ f=c=='-'?-1:1;c=getchar(); }
    while(c>='0'&&c<='9'){ x=x*10+c-'0';c=getchar(); }
    if(c!='.') return f*x;
    c=getchar(); db y=1;
    while(c>='0'&&c<='9'){ y/=10;x+=(c-'0')*y;c=getchar(); }
    return f*x;
}
void zig(int &u){
    int ls=lc[u];
    lc[u]=rc[ls];
    rc[ls]=u;
    u=ls;
}
void zag(int &u){
    int rs=rc[u];
    rc[u]=lc[rs];
    lc[rs]=u;
    u=rs;
}
int g_pre(int k){
    int u=rt,ans=0;
    while(u){
        if(X[u]<X[k]){ ans=u; u=rc[u]; }
        else u=lc[u];
    }
    return ans;
}
int g_nxt(int k){
    int u=rt,ans=0;
    while(u){
        if(X[u]>X[k]){ ans=u; u=lc[u]; }
        else u=rc[u];
    }
    return ans;
}
db g_k(int a,int b){
    if(!a||!b) return 0;
    return (Y[a]-Y[b])/(X[a]-X[b]);
}
bool insert(int &u,int k){
    if(!u||X[u]==X[k]){
        if(X[u]==X[k]&&Y[k]<=Y[u]) return 0;
        u=k;
        pre[u]=g_pre(u);
        nxt[u]=g_nxt(u);
        if(pre[u]) nxt[pre[u]]=u;
        if(nxt[u]) pre[nxt[u]]=u;
        tk[u]=g_k(u,pre[u]);
        if(nxt[u]) tk[nxt[u]]=g_k(u,nxt[u]);
        p[u]=rand();
        return 1;
    }
    if(X[u]>X[k]){
        bool f=insert(lc[u],k);
        if(p[lc[u]]<p[u]) zig(u);
        return f;
    }
    else{
        bool f=insert(rc[u],k);
        if(p[rc[u]]<p[u]) zag(u);
        return f;
    }
}
void del(int &u,int k){
    if(u==k){
        if(!lc[u]||!rc[u]){ u=lc[u]+rc[u];return; }
        else if(p[lc[u]]<p[rc[u]]){ zig(u);del(rc[u],k); }
        else{ zag(u);del(lc[u],k); }
    }
    else if(X[u]>X[k]) del(lc[u],k);
    else del(rc[u],k);
}
void add(int k){
    X[k]=r[k]*maxn/(a[k]*r[k]+b[k]);
    Y[k]=X[k]/r[k];
    /*Y[k]=maxn/(a[k]*r[k]+b[k]);
    X[k]=Y[k]*r[k];*/           // 这里巨恶心……如果按我注释掉的方法写的话有一个点会 WA ……
    int pr=g_pre(k),nx=g_nxt(k);
    if(nx&&g_k(pr,k)<=g_k(nx,k)) return;
    if(!insert(rt,k)) return;
    while(pre[k]&&tk[k]>tk[pre[k]]){
        del(rt,pre[k]);
        pre[k]=g_pre(k);
        if(pre[k]) nxt[pre[k]]=k;
        tk[k]=g_k(k,pre[k]);
    }
    while(nxt[nxt[k]]&&tk[nxt[k]]<tk[nxt[nxt[k]]]){
        del(rt,nxt[k]);
        nxt[k]=g_nxt(k);
        if(nxt[k]) pre[nxt[k]]=k;
        if(nxt[k]) tk[nxt[k]]=g_k(k,nxt[k]);
    }
}
int k_pre(int k){
    int u=rt,ans=0;
    while(u){
        if(tk[u]>K[k]){ ans=u;u=rc[u]; }
        else u=lc[u];
    }
    return ans;
}
void update(int i){
    K[i]=-a[i]/b[i];
    int j=k_pre(i);
    f[i]=a[i]*X[j]+b[i]*Y[j];
}
void check(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lf%lf",&X[i],&Y[i]);
    for(int i=1;i<=n;i++) add(i);
}
int main(){
    n=(int)read(),f[1]=read();maxn=f[1];
    for(int i=1;i<=n;i++){ 
        a[i]=read();
        b[i]=read();
        r[i]=read();
    }
    add(1);
    for(int i=2;i<=n;i++){
        update(i);
        maxn=max(maxn,f[i]);
        add(i);
    }
    printf("%.3lf\n",maxn);
    return 0;
}