题意：给你N个的任务一定要在每天的[Li,Ri]时段完成，然后你只有K天的时间，每个任务有个val，然后求K天里能够获得的最大bonus。
思路：拿到手第一直觉是最小费用最大流，然后不会建图，就跑去想dp去了。好吧最小费用最大流的做法是这样的。首先题目给的是时间，所以变成整数的区间再离散化是一个标准姿势啦。然后对于相邻的时间点 1，2，3，4顺次建立这样的边 1->2->3->4...，边的容量为inf,费用为0.然后对于源点s，我们向时间点1连一条容量为k，费用为0的边，目的是限流。最后由最后一个时间点向汇点t连一条容量为inf,费用为0的边。然后对于每个事件，li,ri,vi,由时间点li->ri连容量为1费用为-vi的边。跑一遍最大流就可以了，最后的答案取个相反数（因为这里其实是最大费用最大流）。考虑一下正确性，首先一定是可以满流的，然后对于每条流出的流量，它只能往右走不能往左走，保证了区间不相交，所以最后跑出来的就是答案。
#pragma warning(disable:4996)
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
#define maxn 10000
#define maxe 30000
#define inf 0x3f3f3f3f
using namespace std;
struct Edge{
int u, v, nxt, cap, cost;
}edge[maxe];
int head[maxn];
int n, m;
int k;
int siz;
struct MinCostMaxFlow
{
queue<int> que;
int add; // edges number
int vn; // total vertex number
int cost[maxn], in[maxn], pre[maxn];
bool vis[maxn];
void init(){
add = 0; vn = siz + 10; memset(head, -1, sizeof(head));
while (!que.empty()) que.pop();
}
void insert(int u, int v, int w, int c){
edge[add].u = u; edge[add].v = v; edge[add].cap = w; edge[add].cost = c;
edge[add].nxt = head[u]; head[u] = add++;
edge[add].u = v; edge[add].v = u; edge[add].cap = 0; edge[add].cost = -c;
edge[add].nxt = head[v]; head[v] = add++;
}
bool spfa(int s, int e){
memset(cost, 0x3f3f3f3f, sizeof(cost));
memset(in, 0, sizeof(in));
memset(vis, 0, sizeof(vis));
cost[s] = 0; pre[s] = -1;
que.push(s); vis[s] = true; in[s]++;
while (!que.empty()){
int u = que.front(); que.pop();
vis[u] = false;
for (int i = head[u]; i != -1; i = edge[i].nxt){
int v = edge[i].v;
if (edge[i].cap > 0 && cost[v] > cost[u] + edge[i].cost){
cost[v] = cost[u] + edge[i].cost; pre[v] = i;
if (!vis[v]){
que.push(v); vis[v] = true; in[v]++;
if (in[v] > vn) return false;
}
}
}
}
if (cost[e] < inf) return true;
else return false;
}
int mincostmaxflow(int s, int e){
int mincost = 0, maxflow = 0;
while (spfa(s, e)){
int flow = inf;
for (int i = pre[e]; i != -1; i = pre[edge[i].u]){
flow = min(flow, edge[i].cap);
}
maxflow += flow;
for (int i = pre[e]; i != -1; i = pre[edge[i].u]){
edge[i].cap -= flow;
edge[i ^ 1].cap += flow;
}
mincost += cost[e] * flow;
}
return mincost;
}
}net;
struct Seg
{
int l, r;
int val;
}seg[maxn];
int dis[maxn]; int top;
int main()
{
while (cin >> n >> k){
int hi, mi, si;
top = 0;
for (int i = 0; i < n; i++){
scanf("%d:%d:%d", &hi, &mi, &si);
seg[i].l = hi * 60*60 + mi * 60 + si;
dis[top++] = seg[i].l;
scanf("%d:%d:%d", &hi, &mi, &si);
seg[i].r = hi * 60*60 + mi * 60 + si;
dis[top++] = seg[i].r;
scanf("%d", &seg[i].val);
}
sort(dis, dis + top);
siz = unique(dis, dis + top) - dis;
for (int i = 0; i < n; i++){
seg[i].l = lower_bound(dis, dis + siz, seg[i].l) - dis + 1;
seg[i].r = lower_bound(dis, dis + siz, seg[i].r) - dis + 1;
}
net.init();
int s = siz + 1, t = s + 1;
for (int i = 1; i <= siz - 1; i++) net.insert(i, i + 1, inf, 0);
net.insert(s, 1, k, 0);
net.insert(siz, t, inf, 0);
for (int i = 0; i < n; i++){
net.insert(seg[i].l, seg[i].r, 1, -seg[i].val);
}
cout << -net.mincostmaxflow(s, t) << endl;
}
return 0;
}