「BZOJ1492」[NOI2007] 货币兑换Cash
Description
Input
第一行两个正整数N、S，分别表示小Y 能预知的天数以及初始时拥有的钱数。 接下来N 行，第K 行三个实数AK、BK、RateK，意义如题目中所述
Output
只有一个实数MaxProfit，表示第N 天的操作结束时能够获得的最大的金钱 数目。答案保留3 位小数。
Sample Input
3 100
1 1 1
1 2 2
2 2 3
1 1 1
1 2 2
2 2 3
Sample Output
225.000
HINT
测试数据设计使得精度误差不会超过10-7。
对于40%的测试数据，满足N ≤ 10；
对于60%的测试数据，满足N ≤ 1 000；
对于100%的测试数据，满足N ≤ 100 000；
题解
此题见cdq论文
首先n^2的dp很好做
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #define inf 0x7fffffff #define ll long long using namespace std; int n,s; double a[100005],b[100005],rate[100005]; double f[100005],ans; int main() { //freopen("cash.in","r",stdin); //freopen("cash.out","w",stdout); scanf("%d%d",&n,&s); for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&a[i],&b[i],&rate[i]); ans=s; f[1]=s*rate[1]/(a[1]*rate[1]+b[1]); for(int i=2;i<=n;i++) { for(int j=1;j<i;j++) ans=max(ans,f[j]*a[i]+f[j]/rate[j]*b[i]); f[i]=ans*rate[i]/(a[i]*rate[i]+b[i]); } printf("%.3lf",ans); return 0; } |
额然后是cdq分治
理论不是很难但是没写过还是比较蛋疼
理论就看cdq论文即可。。。然后代码。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define eps 1e-9 #define inf 0x7fffffff #define ll long long using namespace std; int n,top,stack[100005]; double f[100005]; struct point{double x,y,a,b,k,rate;int w,id;}p[100005],t[100005]; double getk(int a,int b) { if(!b)return -1e20; if(fabs(p[a].x-p[b].x)<eps)return 1e20; return (p[b].y-p[a].y)/(p[b].x-p[a].x); } inline bool operator<(point a,point b){return a.k>b.k;} void solve(int l,int r) { if(l==r) { f[l]=max(f[l],f[l-1]); p[l].y=f[l]/(p[l].a*p[l].rate+p[l].b); p[l].x=p[l].rate*p[l].y; return; }//分治到底了显然我们可以直接计算出结果 int l1,l2,mid=(l+r)>>1,j=1; //============================================================================ l1=l;l2=mid+1; for(int i=l;i<=r;i++) if(p[i].id<=mid)t[l1++]=p[i]; else t[l2++]=p[i]; for(int i=l;i<=r;i++)p[i]=t[i]; //============================================================================ //这一部分是要将一块原顺序分为左右两块 solve(l,mid);//递归左边 top=0; for(int i=l;i<=mid;i++) { while(top>1&&getk(stack[top-1],stack[top])<getk(stack[top-1],i)+eps) top--; stack[++top]=i; }//左边维护一个凸包 stack[++top]=0; for(int i=mid+1;i<=r;i++) { while(j<top&&getk(stack[j],stack[j+1])+eps>p[i].k)j++;//用左边的点作为决策更新右边 f[p[i].id]=max(f[p[i].id],p[stack[j]].x*p[i].a+p[stack[j]].y*p[i].b); } solve(mid+1,r);//递归右边 l1=l;l2=mid+1; for(int i=l;i<=r;i++) if(((p[l1].x<p[l2].x||(fabs(p[l1].x-p[l2].x)<eps&&p[l1].y<p[l2].y))||l2>r)&&l1<=mid)t[i]=p[l1++]; else t[i]=p[l2++]; for(int i=l;i<=r;i++)p[i]=t[i]; } int main() { //============================================================================ //freopen("cash.in","r",stdin); //freopen("cash.out","w",stdout); scanf("%d%lf",&n,&f[0]); for(int i=1;i<=n;i++) { scanf("%lf%lf%lf",&p[i].a,&p[i].b,&p[i].rate); p[i].k=-p[i].a/p[i].b;p[i].id=i; } //============================================================================ sort(p+1,p+n+1);//这里按照斜率进行排序，保证分治的每一块斜率是有序的 solve(1,n); printf("%.3lf",f[n]); return 0; } |
计数器 9861706
OI 课件=>
OI 课件=>
黄学长，可以问下CDQ中最后那个sort是为什么吗？？？
黄学长第43行写错了>_<
好像都一样QAQ
黄学长那个分治过不了编译，暴力好像也是不对的
I’m MaoDick
orz
46行貌似应该叫“维护凸线”吧。。。
催~更。。。。。
233
ORZ！！！求HZWER学长教我CDQ分治