BeJing ICPC 2007 Jewel Trading

acmicpc-live-archive.uva.es/nuevoportal/
题目在UVA上。。。
这道题首先可以列个Dp方程出来
设F[n]为还有n次就要以a价格卖出的最大期望收入,那么
F[n]=Max{ (p-F[n-1])/(1+(p-a)^b) }+F[n-1]…p为大于a的整数。。
由于决策有无限个。。一般的Dp都悲剧了。。
一开始我用微积分算出这个式子关于p的导数,然后想直接用数学方法求出最大值,失败了。。
不过我根据数学观察发现这个导数是单调递减的,也就是说这个函数是单峰的,
于是就可以二分搜索出最大值囧。。。
额。。看来前段时间苦学数学也是有好处的囧。。。
Code:
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int maxn=100+1,inf=~0U>>2;
int n,a;double b,F[maxn];
int main()
{
//freopen("in","r",stdin);
for(int num=1;;num++)
{
cin>>n>>a>>b;if(!n)break;
F[0]=a;n–;
for(int i=1;i<=n;i++)
{
int l=a+1,r=inf;
#define get(p) (p-F[i-1])/(1+pow(p-a,b))
while(l+1<r)
{
int m=(l+r)/2;
if(get(m+1)-get(m)>=0)
l=m;
else
r=m;
}
F[i]=max(get(l),get(r))+F[i-1];
}
printf("Case %d: %0.2lfn",num,F[n]);
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>