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

题面

思路

先假设我们已经知道了操作顺序，考虑如何求出时间。用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
#include
#include
#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]) = 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<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！