这个题真的是太神了。。。
从一開始枚举到最后n方的转化，各种优化基本都用到了极致。。。。
FQW的题解写了好多，个人感觉我全然没有在这里废话的必要了
直接
各种方法真的是应有尽有
大概说下
首先能够想到一个KM算法求二分图最大代权匹配的问题对吧
左边是任务右边是时间
可是这个是三次方啊
那我们就按价值排序，这样就不用代权匹配了可是还是三方
可是左边在右边的连线是单调的。。。
所以就能够贪心推断了。。。
#include#include #include #include #define MAX 5010#define rep(i,j,k) for(int i = j; i <= k; i++)using namespace std;int n, Link[MAX];long long ans = 0;int b[MAX];struct wbysr{ int Begin, end, value;} a[MAX];bool cmp (wbysr a1, wbysr a2){ return a1.Begin < a2.Begin || (a1.Begin == a2.Begin && a1.end < a2.end);}bool cmp2 (wbysr a1, wbysr a2){ return a1.value > a2.value;}bool find (int now, int x){ if (b[x] > a[now].end) return 0; if (!Link[x]) { Link[x] = now; return 1; } int j = Link[x]; if (a[now].end > a[j].end) return find (now,x + 1); else { if (find(j, x + 1)) { Link[x] = now; return 1; } } return 0;}int main(){ scanf ("%d", &n); rep (i, 1, n) scanf ("%d%d%d", &a[i].Begin, &a[i].end, &a[i].value); sort (a + 1, a + 1 + n, cmp); int now = 0; rep (i, 1, n) { now = max (now + 1, a[i].Begin); b[i] = now; } sort (a + 1, a + 1 + n, cmp2); b[n+1] = 0x7fffffff / 3; rep (i, 1, n) { int j; for (j = 1; j <= n; j++) if (b[j] >= a[i].Begin && b[j] <= a[i].end) break; if (find(i, j)) ans += a[i].value; } cout << ans << endl; return 0;}