每笔收入产生的收益是独立的。
计算所有点的收益率，累计。
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std; struct dd{
int d, e;
}ndd[];
struct ddd{
int s, f, r;
}mddd[];
bool dddcomp(ddd a, ddd b)
{
return a.s < b.s;
}
int rate[]; int max(int a, int b)
{
return a>b ? a : b;
}
int main()
{
int t, n, m;
scanf("%d", &t);
for (int w = ; w <= t; ++w){
memset(rate, , sizeof(rate));
scanf("%d %d", &n, &m);
for (int i = ; i < n; ++i)
scanf("%d %d", &ndd[i].d, &ndd[i].e);
for (int i = ; i < m; ++i)
scanf("%d %d %d", &mddd[i].s, &mddd[i].f, &mddd[i].r);
sort(mddd, mddd + m, dddcomp); //读取数据并排序
//求rate[],rate[i]=max(rate[i+1],rate[j]+r[i-j]),只需考虑 r[i-j]存在的情况
int pos = m - ;
for (int i = mddd[m - ].s; i >= mddd[].s; --i){
int mx = rate[i + ];
while (pos >= && i == mddd[pos].s){
mx = max(mx, mddd[pos].r + rate[mddd[pos].f]);
--pos;
}
rate[i] = mx;
}
for (int i = mddd[].s - ; i >= ; --i)
rate[i] = rate[i + ];
//分别计算收入的收益
long long sum = ;
for (int i = ; i < n; ++i){
sum += rate[ndd[i].d] * ndd[i].e;
}
printf("Case #%d:\n%.2lf\n", w, (double)sum / 100.0);
}
}