1492: [NOI2007] Currency conversion Cash

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 3396  Solved: 1434
[Submit][Status][Discuss]

Description

Small Y Recently I worked in a stock exchange . The exchange issues and trades only two types of securities :A Souvenir Ticket ( hereinafter referred to as A Coupon ) and B Souvenir Ticket ( following
abbreviation B Coupon ). Every customer with a coupon has his own account . The number of coupons can be a real number . Every day with the ups and downs of the market ,
Both have their own value at the time , That is, the amount of RMB that can be exchanged for each unit of coupon on the same day . We record the number of K In the day A Coupon and B Coupon Of
The values are AK and BK( element / Unit coupon ). For the convenience of customers , The stock exchange provides a very convenient way of trading : The proportional trading method
. The proportional trading method is divided into two aspects :(a) Sell coupons : The customer offers a [0,100] Real number in OP As a percentage of sales , Its significance is : take
 OP% Of A Coupons and OP% Of B Coupon At that time the value of RMB ;(b) Buy the coupons : Customers pay IP RMB , The exchange will exchange
The total value to users is IP The gold coupon for , also , To satisfy what is offered to customers A Coupons and B The proportion of coupons is in K It happened that RateK; for example , Suppose that
Come down 3 Within days Ak、Bk、RateK The changes are as follows :
Suppose on the first day , Users have 100 element RMB, but without any vouchers . The user can do the following :
be aware , It can be operated many times in the same day . Small Y He is a very economical employee , Through a long period of operation and market estimation , He has
Knowing the future N Within days A Coupons and B The value of the voucher and Rate. He also wants to be able to work it out , If you start with S Yuan , that N At most in a few days
How much is enough .

Input

Enter two positive integers on the first line N、S, They are small Y The number of days you can predict and the amount of money you have initially . Next N That's ok , The first K Row three real numbers AK、B
K、RateK, The meaning is described in the title . about 100% Test data for , Satisfy :0<AK≤10;0<BK≤10;0<RateK≤100;MaxProfit≤1
0^9.
【 Tips 】
1. The input file can be large , Please use a quick read in method .
2. There must be an optimal trading scheme to satisfy :
Each buying operation USES up all the yuan ;
Every time I sell, I sell all of my gold notes .

Output

There's only one real number MaxProfit, It means the first one N The maximum amount of money you can get at the end of a day's operation . The answer is reserved 3 Decimal place .

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

HINT

Source

Solution

Slope optimization DP, Typical is not monotonous

$f[i]=max(f[i],f[j]/(a[j]*rate[j]+b[j])*rate[j]*a[i]+f[j]/(a[j]*rate[j]+b[j])*b[i])$

as for CDQ The theory of partition : Walk   Over and over

inspire :

1. Slope optimization DP There are thousands of changes ..

2. Mastering the divide and conquer algorithm can produce many magical effects (xyx I seem to like divide and conquer very much )

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 200010
struct DayNode
{
double A,B,Ra,k; int id;
bool operator < (const DayNode & T) const
{return k<T.k;}
}a[maxn],tmpa[maxn];
struct PointNode{double x,y;}p[maxn],tmpp[maxn];
int N;
double dp[maxn];
int tmp1[maxn],tmp2[maxn],stack[maxn];
#define inf 1e9
#define eps 1e-9
double slope(int l1,int l2)
{
if (!l1) return -inf;
if (!l2) return inf;
if (fabs(p[l1].x-p[l2].x)<=eps) return -inf;
return (p[l1].y-p[l2].y)/(p[l1].x-p[l2].x);
}
void CDQ(int l,int r)
{
if (l==r)
{
dp[l]=max(dp[l],dp[l-]);
p[l].y=dp[l]/(a[l].Ra*a[l].A+a[l].B);
p[l].x=a[l].Ra*p[l].y;
return;
}
int mid=(l+r)>>,L,R;
L=l; R=mid+;
for (int i=l; i<=r; i++)
if (a[i].id<=mid) tmpa[L++]=a[i]; else tmpa[R++]=a[i];
for (int i=l; i<=r; i++) a[i]=tmpa[i];
CDQ(l,mid);
int top=;
for (int i=l; i<=mid; i++)
{
while (top> && slope(stack[top],stack[top-])<slope(i,stack[top-])+eps) top--;
stack[++top]=i;
}
int Top=;
for (int i=r; i>=mid+; i--)
{
while (Top<top && slope(stack[Top],stack[Top+])+eps>a[i].k) Top++;
dp[a[i].id]=max(dp[a[i].id],p[stack[Top]].x*a[i].A+p[stack[Top]].y*a[i].B);
}
CDQ(mid+,r);
L=l; R=mid+;
for (int i=l; i<=r; i++)
if (((p[L].x<p[R].x+eps || (fabs(p[L].x-p[R].x)<=eps && p[L].y<p[R].y+eps)) || R>r) && L<=mid)
tmpp[i]=p[L++];
else tmpp[i]=p[R++];
for (int i=l; i<=r; i++) p[i]=tmpp[i];
}
int main()
{
scanf("%d%lf",&N,&dp[]);
for (int i=; i<=N; i++)
scanf("%lf%lf%lf",&a[i].A,&a[i].B,&a[i].Ra),a[i].k=-a[i].A/a[i].B,a[i].id=i;
sort(a+,a+N+);
CDQ(,N);
//for (int i=1; i<=N; i++) printf("%d %d %.3lf %.3lf %.3lf %.3lf \n",i,a[i].id,a[i].A,a[i].B,a[i].Ra,a[i].k);
printf("%.3lf\n",dp[N]);
return ;
}

【BZOJ-1492】 Currency conversion Cash DP + Slope optimization + CDQ More articles on divide and conquer

  1. BZOJ.1492.[NOI2007] Currency conversion (DP Slope optimization CDQ Divide and conquer /Splay)

    BZOJ Luogu If you can make money one day , Then I will sell all the gold coupons on this day . Also, if one day you want to buy , I'm sure I'll spend all my money . So make \(f_i\) To \(i\) The most money a day has ( At this point, I don't have any coupons ), You can choose ...

  2. Luogu .4655.[CEOI2017]Building Bridges(DP Slope optimization CDQ Divide and conquer )

    LOJ Luogu \(f_i=s_{i-1}+h_i^2+\min\{f_j-s_j+h_j^2-2h_i2h_j\}\), Obviously, we can optimize the slope . \(f_i-s_{i-1}-h_i^2+2h_ih_j=f_ ...

  3. BZOJ_3963_[WF2011]MachineWorks_ Slope optimization +CDQ Divide and conquer

    BZOJ_3963_[WF2011]MachineWorks_ Slope optimization +CDQ Divide and conquer Description You're an arbitrary complex machine company (Arbitrarily Complex Machines, ACM) ...

  4. [BZOJ1492][NOI2007] Currency conversion Cash( Slope optimization +CDQ Divide and conquer )

    1492: [NOI2007] Currency conversion Cash Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 5838  Solved: 2345[Submit][Sta ...

  5. 【BZOJ1492】[NOI2007] Currency conversion Cash Slope optimization +cdq Divide and conquer

    [BZOJ10492][NOI2007] Currency conversion Cash Description Small Y Recently I worked in a stock exchange . The exchange issues and trades only two types of securities :A Souvenir Ticket ( hereinafter referred to as A Coupon ) and B Souvenir Ticket ( hereinafter referred to as B Coupon ). Every time ...

  6. Luogu P4027 [NOI2007] Currency conversion (dp Slope optimization cdq Two points )

    The question Topic link Sol The key to solving the problem is to see the tips in the title ... set up \(f[i]\) To \(i\) The maximum number of soft coins held by Tian , The obvious answer is \(max_{i = 1}^n f[i]\) Transfer to \(f_i = ...

  7. BZOJ 1492 Currency conversion Cash CDQ Divide and conquer

    This question n2 The algorithm is a process of maintaining the upper convex hull . It can also be used. CDQ Divide and conquer . my CDQ Divide and conquer is not the same as online , Use the points on the left to create a convex hull , The dot on the right is on the top two . The advantage is clear thinking , The insertion and deletion of convex hull are avoided , The disadvantage is one more l ...

  8. LUOGU P4027 [NOI2007] Currency conversion ( Slope optimization +CDQ Divide and conquer )

    Portal Their thinking There are two sentences in the title , Either buy it all or sell it all , therefore dp The equation is easier to set up ,f[i]=max(f[j]*rate[j]*a[i])/(rate[j]*a[j]+b[j])+(f[j]*b ...

  9. bzoj1492/luogu4027 Currency conversion ( Slope optimization +cdq Divide and conquer )

    set up f[i] It's No i The maximum amount of money you can get in a day , that f[i]=max{ In the j Day use f[j] I want to buy , Then in the first i God's money ,f[i-1]} And then solve an equation or something , set up $x[j]=\frac{F[j]}{A[j]*Ra ...

Random recommendation

  1. C++11 New feature learning

    http://www.cprogramming.com/c++11/c++11-lambda-closures.html

  2. jQuery1.9.1-- Structure and $ Method working principle, source code analysis

    jQuery Of $ Methods are very versatile , The interface is so flexible , It's a little bit against the principle of design pattern, single responsibility . But users like it very much , Because you don't have to remember so many names , I just need to remember one $ You can do a lot of things , This $ It's like a universal ...

  3. AIX Project summary _oracle_sqlloader_01

    I've been busy lately AIX The migration items of , But also because of their own little lazy , So it's only now that we've started recording . Next , Get down to business . In this project , Learning shell Related knowledge , From the basic syntax commands ( Defining variables . Special variables use . Cycle control . Method calls, etc ) To l ...

  4. Rookie jQuery Source learning notes ( Preface )

    Preface I believe any front-end developer or front-end enthusiast is right jQuery No stranger .jQuery Simple and easy to use , Powerful , Especially with good browser compatibility , It greatly reduces the difficulty of front-end development , Make front-end development become “ Be approachable ”. Since I ...

  5. Java Advanced memory management and garbage collection

    Java Is in JVM Running in the virtual memory environment . Memory is divided into stacks (stack) And heaps (heap) Two parts . We're going to look at these two areas separately . Stack stay Java in ,JVM The stack in records the thread's method calls . Each thread has a stack . In a certain ...

  6. Asp.net MVC-3- Execution process

    This article mainly talks about MVC Created when processing a request Controller And execution Action Complete process . establish Controller To look at first MvcHandler How to handle requests in BeginProcessRequest: pro ...

  7. app Back end design (2)--xmpp Use (2014.01.14 to update )

    stay app Sometimes you need to add a chat service , Let's talk about our experience in developing chat service : (1) Chat server selected openfire, This is a base xmpp Protocol chat server (XMPP It's based on XML The agreement , It's inherited in XML Environmental Science ...

  8. ASP.NET MVC5 Advanced programming And Ajax

    jQuery Not only does it support all modern browsers , Include IE.Firefox.Safari.Opera and Chrome etc. , You can also write code and browser API Hide inconsistencies in case of conflict ( And mistakes ). 1. jQuery jQuery Be good at ...

  9. tomcat 8 Online management admin To configure

    stay tomcat8 Next , Pay more attention to safety . If you want to deploy the application in the management console , More configuration needs to be modified . stay $tomcat_base$/webapps/manager/META-INF/context.xml in add to ...

  10. C#5 There are two ways to generate thumbnails

    using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.D ...