题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4833
这道题目关键的思想是从后往前dp，dp[i]表示在第i处投资xi能获得的最大收益，其中xi表示从第i-1到第i处投资之间的收入总和（不包括收益），也就是用xi这些钱从第i处开始投资到最后靠xi这些钱获得的最大收益。那么获得的总收益就是dp[0] * x0 + dp[1] * x1 + ... + dp[n] * xn。另一个关键思想就是对理财产品的起始和结束时间进行离散化，这样能够节约空间和dp的时间。
#include <stdio.h>
#include <vector>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std; int dates[], ls[ * ], jg[ * ];
long long dp[ * ], ans;
struct Product
{
int start, finish, rate;
}product[];
map<int, int> myMap;
vector<int> vec1[ * ], vec2[ * ]; #define max(a, b) ((a) > (b) ? (a) : (b)) int main(void)
{
int n, m, t, i, j, k, date, earning, cnt, maxDate; scanf("%d", &t);
for (i = ; i <= t; i++)
{
scanf("%d%d", &n, &m);
memset(dates, , sizeof(dates));
maxDate = ;
for (j = ; j < n; j++)
{
scanf("%d%d", &date, &earning);
dates[date] += earning;
if (date > maxDate)
maxDate = date;
}
for (j = ; j < m; j++)
{
scanf("%d%d%d", &product[j].start, &product[j].finish, &product[j].rate);
ls[j] = product[j].start;
ls[j + m] = product[j].finish;
if (product[j].finish > maxDate)
maxDate = product[j].finish;
}
for (j = ; j <= maxDate; j++)
dates[j] += dates[j - ];
sort(ls, ls + m + m, less<int>());
cnt = unique(ls, ls + m + m) - ls;
jg[] = dates[ls[]];
myMap.clear();
for (j = ; j < cnt; j++)
{
myMap[ls[j]] = j;
jg[j] = dates[ls[j]] - dates[ls[j - ]];
vec1[j].clear();
vec2[j].clear();
}
for (j = ; j < m; j++)
{
vec1[myMap[product[j].start]].push_back(myMap[product[j].finish]);
vec2[myMap[product[j].start]].push_back(product[j].rate);
}
memset(dp, , sizeof(dp));
for (j = cnt - ; j >= ; j--)
{
dp[j] = dp[j + ];
for (k = ; k < vec1[j].size(); k++)
dp[j] = max(dp[j], dp[vec1[j][k]] + vec2[j][k]);
}
ans = ;
for (j = ; j < cnt; j++)
ans += dp[j] * jg[j];
printf("Case #%d:\n%.2lf\n", i, (double)ans / 100.0);
}
return ;
}