欧意交易所app官方下载[NOI2007]货币兑换_欧意交易所-欧意app官方下载平台

货币兑换题解

很容易发现，如果在第i天买并在第j天卖时可以得到更多的价值，那我们如果要在j天卖的话，就应该在第i天把钱花完去买股票。

我们设

$f_{i}$

为到第i天时可以得到的最大钱数，这样的话可以得到的两种金券数为

$x_{i}= \frac{f_{i}R_{i}}{a_{i}R{i}+ b_{i}}$

，

$y_{i}=\frac{f_{i}}{a_{i}R_{i}+b_{i}}$

。，于是，我们得到

$f_{j}= x_{i}a_{j}+ y_{i}b_{j}$

。

可以得到

$y_{i}= -\frac{a_{j}x_{i}}{b_{j}}+\frac{f_{j}}{b_{j}}$

。于是对于平面上的

$\left ( x_{i},y_{i} \right )$

，当它被

$k=-\frac{a_{j}}{b_{j}}$

所切时，它的最大截距就是最优的决策。

求得最大截距的方法也很简单，这就相当于维护点之间的一个凸包。对于一个点j，若其左边的线的斜率比它的斜率小，那它斜率的情况肯定是更优的，我们需要将其左移。若右边斜率比他大，就要将其右移。

之后，就只需要维护这个凸包了。我们可以通过splay与CDQ两种方式来维护，这里选的是CDQ。

我们只需要对决策的日子这一维进行二分，先保证

$k=-\frac{a}{b}$

的顺序，在二分时将左区间通过x值排序。再将左区间的斜率凸包进行维护，更新右区间的dp值即可。

源码 #include<cstdio> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<queue> #include<map> #include<set> using namespace std; #define MAXN 100010 typedef long long LL; #define int LL const double eps=1e-9; const double INF=1e9; typedef pair<int,int> pii; template<typename _T> void read(_T &x){ _T f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();} while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();} x*=f; } template<typename _T> _T Fabs(_T x){return x<0?-x:x;} int n,sta[MAXN],stak; double f[MAXN]; struct ming{double a,b,k,r,x,y;int id;}q[MAXN],p[MAXN]; int cmp(ming x,ming y){return x.k<y.k;} double X(int i){return q[i].x;} double Y(int i){return q[i].y;} double slope(int i,int j){ if(Fabs(X(i)-X(j))<=eps)return INF; return (Y(i)-Y(j))/(X(i)-X(j)); } void merge(int l,int r){ if(l==r){ f[l]=max(f[l],f[l-1]); q[l].y=f[l]/(q[l].a*q[l].r+q[l].b); q[l].x=q[l].y*q[l].r; //printf("%d:%lf %lf %lf %d\n",l,q[l].x,q[l].y,f[l],q[l].id); return ; } int mid=l+r>>1,j=l-1,k=mid; for(int i=l;i<=r;i++) if(q[i].id<=mid)p[++j]=q[i]; else p[++k]=q[i]; for(int i=l;i<=r;i++)q[i]=p[i];//,printf("%d:%d\n",i,q[i].id); merge(l,mid);stak=0; for(int i=l;i<=mid;i++){ while(stak>=2&&slope(sta[stak],i)+eps>slope(sta[stak-1],sta[stak]))--stak; sta[++stak]=i;//printf("%d %d %d:%lf\n",l,r,stak,slope(sta[stak-1],sta[stak])); } for(int i=mid+1;i<=r;i++){ while(stak>=2&&slope(sta[stak-1],sta[stak])<=q[i].k+eps)--stak; int t=sta[stak];f[q[i].id]=max(f[q[i].id],q[t].x*q[i].a+q[t].y*q[i].b); //printf("%d %d %d:%d %lf %lf\n",l,r,q[i].id,t,q[i].k,f[q[i].id]); } merge(mid+1,r);j=l;k=mid+1; for(int i=l;i<=r;i++) if(j<=mid&&(k>r||q[j].x<q[k].x+eps)) p[i]=q[j],++j; else p[i]=q[k],++k; for(int i=l;i<=r;i++)q[i]=p[i];//,printf("%d:%d\n",i,q[i].id); } signed main(){ scanf("%d %lf",&n,&f[0]); for(int i=1;i<=n;i++){ scanf("%lf %lf %lf",&q[i].a,&q[i].b,&q[i].r); q[i].k=-q[i].a/q[i].b;q[i].id=i; } sort(q+1,q+n+1,cmp);merge(1,n); printf("%.3lf",f[n]); return 0; } 谢谢！！！

(责任编辑：)

搜索

热门标签:

欧意交易所app官方下载[NOI2007]货币兑换