Best Financing
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 29 Accepted Submission(s): 3
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
每组数据格式如下：
第一行是n m
之后连续n行，每行为两个以空格分隔的整数，依次为date和earning
之后连续m行，每行为三个以空格分隔的整数，依次为start, finish和interest_rate
Output
对第i组数据，i从1开始计，输出
Case #i:
收益数值，保留小数点后两位，四舍五入。
Case #i:
收益数值，保留小数点后两位，四舍五入。
Sample Input
2
1 2
1 10000
1 100 5
50 200 10
2 2
1 10000
5 20000
1 5 6
5 9 7
1 2
1 10000
1 100 5
50 200 10
2 2
1 10000
5 20000
1 5 6
5 9 7
Sample Output
Case #1:
1000.00
Case #2:
2700.00
1000.00
Case #2:
2700.00
Source
这个问题主要是进行转化。
把投资点进行离散化，就可以看成从每个投资点出发可以最多赚多少钱。
每个投资点前面一段是属于这个点的钱。
然后n^2的DP进行处理。
/* ***********************************************
Author :kuangbin
Created Time :2014/5/25 16:13:32
File Name :E:\2014ACM\比赛\百度之星初赛2\C.cpp
************************************************ */ #include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct NN1
{
int d,e;
void input()
{
scanf("%d%d",&d,&e);
}
}node1[];
struct NN2
{
int start,finish;
int r;
void input()
{
scanf("%d%d%d",&start,&finish,&r);
}
}node2[];
int a[];
long long f[];
long long f2[];
int dp[]; vector<int>vec[];
vector<int>vec2[];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T;
int iCase = ;
int n,m;
scanf("%d",&T);
while(T--)
{
iCase++;
printf("Case #%d:\n",iCase);
scanf("%d%d",&n,&m);
int cnt = ;
memset(f,,sizeof(f));
for(int i = ;i < n;i++)
{
node1[i].input();
//a[cnt++] = node1[i].d;
f[node1[i].d] += node1[i].e;
}
for(int i = ;i <= ;i++)
f[i] += f[i-];
for(int i = ;i < m;i++)
{
node2[i].input();
a[cnt++] = node2[i].start;
a[cnt++] = node2[i].finish;
}
sort(a,a+cnt);
cnt = unique(a,a+cnt) - a;
map<int,int>mp;
for(int i = ;i < cnt;i++)
mp[a[i]] = i;
f2[] = f[a[]];
for(int i = ;i < cnt;i++)
f2[i] = f[a[i]] - f[a[i-]];
for(int i = ;i < cnt;i++)
{
vec[i].clear();
vec2[i].clear();
}
for(int i = ;i < m;i++)
{
node2[i].start = mp[node2[i].start];
node2[i].finish = mp[node2[i].finish];
vec[node2[i].start].push_back(node2[i].finish);
vec2[node2[i].start].push_back(node2[i].r);
}
memset(dp,,sizeof(dp));
for(int i = cnt-;i >= ;i--)
{
dp[i] = dp[i+];
int sz = vec[i].size();
for(int j = ;j < sz;j++)
dp[i] = max(dp[i],dp[vec[i][j]] + vec2[i][j]);
}
long long ans ;
//minCostMaxflow(cnt,cnt+1,ans);
ans = ;
for(int i = ;i < cnt;i++)
{
ans += (long long)dp[i]*f2[i];
}
printf("%.2lf\n",(double)ans/); }
return ;
}