day12

正睿停课

T1

T2

#109. 【17 提高 7】当那一天来临

首先考虑确定了工作顺序如何计算时间。

模拟？

$dp[i][j](i \in [1,n], j\in[1,3])$表示到了第i个物品，已经被前j个机器加工完了。
$dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])+a[i][j]$表示第i个物品如果要被第j个机器加工，必须等这个物品被前一个机器加工完，而且也要等这个机器加工完它前面的物品，取一个最大值，然后发现这个dp就是在3*n的矩阵上求一个从(0,0)到(3,n)的最长路。

然后考虑如何确定顺序。
题目中保证了第二行一定小于第三行，那么最长路一定是经过第二行一个点。
考虑两列，是否交换。
两列初始时是这样的，交换完也只会影响两条路径。
经过这两列的最大的路径：两个蓝色+max(红，绿）
所以分别计算交换前和交换后的最大路径，如果交换后小了，就交换。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 100005;
struct Node{
    int a, b, c;
}A[N];
LL sa[N], sc[N];
bool operator < (const Node &x, const Node &y) {
    return x.a + y.c + max(x.b + x.c, y.a + y.b) < y.a + x.c + max(y.b + y.c, x.a + x.b);
}
int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        A[i].a = read(), A[i].b = read(), A[i].c = read();
    }
    sort(A + 1, A + n + 1);
    for (int i = 1; i <= n; ++i) sa[i] += sa[i - 1] + A[i].a;
    for (int i = n; i >= 1; --i) sc[i] += sc[i + 1] + A[i].c;
    LL ans = 0;
    for (int i = 1; i <= n; ++i) 
        ans = max(ans, sa[i] + A[i].b + sc[i]);
    cout << ans;
    return 0;
}
/*
3
5 3 4
3 2 9
3 4 8
*/