思路

先假设我们已经知道了操作顺序，考虑如何求出时间。用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的转移矩阵

[ZROJ110][假如战争今天爆发]

发现其实f[i][j]表示的是从(1,1)这个点走到(j,i)的最长路径。

然后我们再去考虑操作顺序。显然我们想让从(1,1)到(3,n)最长的路径最短。

然后考虑贪心。用到一种和国王游戏类似的贪心方法。我们先只考虑两个点之间应该怎样比较，然后就可以考虑全局。可以证明，因为B比C小，所以要想跑最长的路径，那么只在B这一行停留一下是最优秀的，然后就是考虑从那个位置从A行走到C行就可以了。

[ZROJ110][假如战争今天爆发]

如图，我们考虑如果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;

}

一言

真正重要的东西，总是没有的人比拥有的人清楚。 ——银魂