https://codeforces.com/gym/101908/problem/F
【题意】
有n个组，每个组有m个区间，区间信息包括开始时间，结束时间，区间价值
你需要选择区间，使得区间价值和最大，并且保证每个组都能被选择一次
【思路】
将所有区间按左端点存在一个vector里，并且保存id属于哪个组别的信息
dp[i][j]表示在数轴的时间点i，当前选择组的状态，遍历所有以i为左端点的区间，更新dp
转移方程：dp[ed][j|(1<<id)]=max(dp[i][j]+val);
注意初始化为-1，因为有可能不构成
【代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int dp[87000][1 << 11];struct node {int ed, val, id;
};vector<node>v[87000];int main()
{int n, m, st, ed, val;while (~scanf("%d", &n)) {for (int i = 1; i <= n; i++) {scanf("%d", &m);while (m--) {scanf("%d%d%d", &st, &ed, &val);v[st].push_back({ ed, val, i });}}memset(dp, -1, sizeof(dp));for (int i = 1; i <= 86400; i++) {dp[i][0] = 0;for (int j = 1; j <= (1 << n) - 1; j++)dp[i][j] = max(dp[i][j], dp[i - 1][j]);for (auto p : v[i]) {int ed = p.ed;int val = p.val;int id = p.id;for (int j = 0; j <= (1 << n) - 1; j++) {if (dp[i][j] == -1) continue;int s = j | 1 << (id - 1);ed = ed;dp[ed][s] = max(dp[ed][s], dp[i][j] + val);}}}printf("%d\n", dp[86400][(1 << n) - 1]);}
}