思路
先假设我们已经知道了操作顺序，考虑如何求出时间。用f[i][j]表示前i个物品，第i个加工完了第j台机器所需要的最少的时间。转移的时候就是f[i][j] = max(f[i-1][j],f[i][j - 1] + a[i][j]) a[i][j]表示第i个物品加工第j台机器所需要的时间。
然后去观察这个dp的转移矩阵
发现其实f[i][j]表示的是从(1,1)这个点走到(j,i)的最长路径。
然后我们再去考虑操作顺序。显然我们想让从(1,1)到(3,n)最长的路径最短。
然后考虑贪心。用到一种和国王游戏类似的贪心方法。我们先只考虑两个点之间应该怎样比较，然后就可以考虑全局。可以证明，因为B比C小，所以要想跑最长的路径，那么只在B这一行停留一下是最优秀的，然后就是考虑从那个位置从A行走到C行就可以了。
如图，我们考虑如果x在前面和y在前面会有什么不同，从那些重发的点如果x在前面，那么这条路径中间这一块的长度就会是A[x]+C[y] + max(B[x]+C[x],A[y] + B[y])。同理，如果y在前面那么这一块的路径长度就会是A[y] + C[x] +max(B[y] +C[y],A[x] + B[y])。然后根据这个进行比较，按照总和比较小的方案排序排序就好了。
拍完序之后可以发现其实不用dp也可以，先预处理出A行的前缀和和C行的后缀和。然后O(n)的枚举转移的改变方向的位置就可以了。
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long ll;
const int N = 100000 + 100;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
struct node{
int a[4];
}e[N];
bool operator < (const node &y,const node &x) {
return y.a[1] + x.a[3] + max(y.a[2] + y.a[3],x.a[1] + x.a[2]) <
y.a[3] + x.a[1] + max(x.a[2] + x.a[3],y.a[1] + y.a[2]);
}
ll sum1[N],sum2[N];
int main() {
int n = read();
for(int i = 1;i <= n;++i)
e[i].a[1] = read(),e[i].a[2] = read(),e[i].a[3] = read();
sort(e + 1,e + n + 1);
for(int i = 1;i <= n;++i)
sum1[i] = sum1[i - 1] + e[i].a[1];
for(int i = n;i >= 1;--i)
sum2[i] = sum2[i + 1] + e[i].a[3];
ll ans = 0;
for(int i = 1;i <= n;++i)
ans = max(ans, sum1[i] + sum2[i] + e[i].a[2]);
cout<<ans;
return 0;
}
一言
真正重要的东西，总是没有的人比拥有的人清楚。 ——银魂