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 .

3 100
1 1 1
1 2 2
2 2 3

225.000

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 ...