2014百度之星预赛(第二场)—

2014百度之星预赛(第二场)——Best Financing

Problem Description

小A想通过合理投资银行理財产品达到收益最大化。已知小A在未来一段时间中的收入情况。描写叙述为两个长度为n的整数数组dates和earnings，表示在第dates[i]天小A收入earnings[i]元（0<=i<n）。银行推出的理財产品均为周期和收益确定的，可描写叙述为长度为m的三个整数数组start、finish和interest_rates, 若购买理財产品i（0<=i<m），须要在第start[i]天投入本金，在第finish[i]天可取回本金和收益。在这期间本金和收益都无法取回，收益为本金*interest_rates[i]/100.0。

当天取得的收入或理財产品到期取回的本金当天就可以购买理財产品（注意：不考虑复利，即购买理財产品获得的收益不能用于购买兴许的理財产品）。假定闲置的钱没有其它收益。如活期收益等，全部收益仅仅能通过购买这些理財产品获得。求小A能够获得的最大收益。

限制条件:
1<=n<=2500
1<=m<=2500
对于随意i（0<=i<n）,1<=dates[i]<=100000,1<=earnings[i]<=100000, dates中无反复元素。
对于随意i（0<=i<m）,1<=start[i]<finish[i]<=100000, 1<=interest_rates[i]<=100。

Input

第一行为T (T<=200)，表示输入数据组数。
每组数据格式例如以下：
第一行是n m
之后连续n行。每行为两个以空格分隔的整数。依次为date和earning
之后连续m行。每行为三个以空格分隔的整数，依次为start, finish和interest_rate

Output

对第i组数据。i从1開始计，输出
Case #i:
收益数值。保留小数点后两位，四舍五入。

Sample Input

Sample Output

Case #1:
1000.00
Case #2:
2700.00

Source

2014年百度之星程序设计大赛 - 初赛（第二轮）

正确的题意是：

告诉你n个时间点，这些时间点你会得到若干的钱．

然后告诉你m个时间段，以及时间段相应的利率(百分比)．

问最后最多能够得到多少钱．

注意事项

首先收益不能用于购买

当天得到钱后当前能够花出去，也就是当天finish的当天可用于购买．

分析

理解题意后，心中会想到这是道DP题．

然后看看每一个时间点得到的钱。貌似他们之间是相互独立的．

实际上看到这个是独立的后，就非常好做了．

对于某个时间点的钱，我们随着时间的向后流动，会遇到一些时间段．

对于遇到的时间段，我们有两个选择：１．买; ２．不买.

买了我们的时间就移动到这个时间段的结束时间，不买了我们的时间移动到下一刻．

最后得到的钱是：　当前钱　＊　选择的时间段的利率的和．

建议自己画一个图看看，或者自己心里面想想．

因为我们的目标是是收益最大，也就是是选择的时间段的利率和最大．

这个问题能够轻松的写出状态转移方程：

dp[ i ] = max( dp[i],  dp[j] + rate[i, j]);

当中　dp[ i ] 代表　i 时间点到终于时间的路线上最大的利率和。　dp[i] 的初始值能够是　dp[i + 1], 即不选择以这个时间点開始的时间段．

rate[i, j] 代表有个从　i 到　j 的时间段。且这个时间段的利率是　rate[i, j].

这样我们从后向前扫描一遍就能够预处理全部时间点到终于时间的最大利率．

然后我们用当前时间的钱　乘以　当前时间的最优利率和就是当前的最大利益．

以上分析来自博文:http://tiankonguse.com/record/record.php?id=670

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 100005

using namespace std;

typedef struct Money
{
	int dates;
	int earnings;
}Money;

typedef struct Earn
{
	int start;
	int finish;
	int rate;
}Earn;

bool cmp(const Earn &l,const Earn &r)
{
	return l.start<r.start;
}

int dp[MAX];
Money money[MAX];
Earn earn[MAX];
int n,m,maxtime;
long long ans;

void DP()
{
	memset(dp,0,sizeof(dp));
	m--;
	for(int i=maxtime;i>=0;i--)
	{
		dp[i]=dp[i+1];
		while(m>=0&&i==earn[m].start)
		{
			dp[i]=max(dp[i],dp[earn[m].finish]+earn[m].rate);
			m--;
		}
	}
}

int main(int argc,char *argv[])
{
	int t;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&m);
		maxtime=0;
		for(int j=0;j<n;j++)
		{
			scanf("%d%d",&money[j].dates,&money[j].earnings);
			maxtime=max(maxtime,money[j].dates);
		}
		for(int k=0;k<m;k++)
		{
			scanf("%d%d%d",&earn[k].start,&earn[k].finish,&earn[k].rate);
			maxtime=max(maxtime,earn[k].finish);
		}
		sort(earn,earn+m,cmp);
		DP();
		ans=0;
		for(int j=0;j<n;j++)
			ans+=money[j].earnings*dp[money[j].dates];
		printf("Case #%d:
",i);
		printf("%I64d.%02I64d
",ans/100,ans%100);
	}
	return 0;
}