Code Level: ※
Thinking Level: ※※

Description

N件物品，每件物品要被三个机器依次加工，时间分别为

$A_i,B_i,C_i(max_{B_i}<=min_{C_i})$

Solution

问题在于确定加工顺序；
我们观察一个加工顺序所具有的性质
即，令D(i,j)表示加工到第i件物品，第j个机器（j取0，1，2）所需要的最小时间
那么

$D_{i,j}=max(D_{i,j-1},D_{i-1,j})+A_{i,j}$

其中

$A_{i,j}表示第i件物品第j个机器加工时间$

将其想象为图
可以发现所求的即是1，1到N，3的最长路径
观察题中性质

$min(C_i)>=max(B_i)$

即，一条最长路径只会经过第二个机器一次以得到更多的第三个机器的权值叠加

现在，我们便可以得出最优图的构建方案
对于两件物品，我们通过比较它们二者相互的贡献来确定方案即可

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int nn=100005;
int n;
struct dat{
    int a,b,c;
    friend bool operator<(dat a,dat b){
        return max(a.a+b.a+b.b+b.c,a.a+a.b+a.c+b.c)<max(b.a+a.a+a.b+a.c,b.a+b.b+b.c+a.c);
    }
}e[nn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
    sort(e+1,e+1+n);
    ll aa=0,bb=0,cc=0;
    for(int i=1;i<=n;i++){
        aa=aa+e[i].a; 
        bb=max(aa,bb)+e[i].b;
        cc=max(bb,cc)+e[i].c;
    }
    printf("%lld\n",cc);
    return 0;
}