华为校招&实习机试在线OJ刷题系统 ｜ 在线OJ注册使用教程
目录
题目
思路
Code
题目
题目内容：
将一个 N 层的深度神经网络按流水线并行部署到 K 个 GPU 上。层必须按从前往后的顺序切成恰好 K 段连续子序列，每段分给一个 GPU，且每段至少包含 1 层。
第 i 层的计算耗时为 Tᵢ，该层输出激活对应的通信耗时为 Sᵢ（层号从 1 到 N）。一段若没有覆盖到第 N 层，总耗时等于段内各层计算耗时之和，再加上该段最后一层的通信耗时；同一段内部的相邻层通信耗时为 0。覆盖到第 N 层的那段没有后继层，通信耗时为 0，总耗时只计计算耗时。
请给出一种切分，使 K 个阶段总耗时的最大值最小，并输出这个最小值。
输入格式：第一行 N 个整数 T₁, T₂, …, T_N，为各层的计算耗时（层数 N 由该行数字个数确定）。第二行 N 个整数 S₁, S₂, …, S_N，为各层输出激活对应的通信耗时。第三行一个整数 K，表示 GPU 个数。
输出格式：输出一个整数，为 K 个阶段总耗时最大值的最小可能值。
样例1
输入：
3 8 6 5 1输出：
11> 注：原文未提供输入/输出描述，本节由官方题解代码推断补全。样例中两层计算耗时为 3、8，通信耗时为 6、5，K=1 时唯一切法是整段一段，覆盖到最后一层不计通信耗时，总耗时 3+8=11。
思路
整体思路：这是「分层切连续段、最小化最大段耗时」的经典线性 DP。段与段首尾相接，最后一段的右端点确定后，前面部分就是一个规模更小的同类子问题，因此用 dp[p][i] 表示前 i 层恰好切成 p 段时最大段耗时的最小值，枚举最后一段的起点转移，答案是 dp[K][N]。
1. 段耗时的定义要先理清：一段从第 L 层到第 R 层，耗时是 T_L+…+T_R，若 R<N 还要加 S_R（这段最后一层输出要跨 GPU 传给下一段），若 R=N 则不计通信。同一段内部相邻层之间不计时。
2. 预处理前缀和 pre[i] = T_1+…+T_i，任意一段的计算耗时 pre[R]−pre[L−1] 就能 O(1) 得到。
3. 转移方程：dp[p][i] = min over 0≤j<i 的 max( dp[p−1][j], cost(j+1, i) )，其中 cost(L,R)=pre[R]−pre[L−1]（R<N 时再加 S_R）。边界 dp[0][0]=0，其余初始化为无穷大；只有 dp[p−1][j] 可达（前 j 层切得出 p−1 段）时 j 才能作为本段起点。
4. 实现上第 p 轮只依赖第 p−1 轮，用一维数组滚动：从第 1 段枚举到第 K 段，每轮枚举右端点 i 和左端点 j，用 max(前缀最优, 本段耗时) 取最小。K=N 时每层单独一段也合法；K≤N 时一定存在合法切分，dp[K][N] 不会是无穷大。
复杂度：时间 O(K×N²)，空间滚动后 O(N)。N、K 在题目常规规模（几百到一千）内都能轻松通过。坑点：通信耗时挂在「段的最后一层」上而不是段的开头；覆盖第 N 层的那段不计时，判断条件是 i==N；无穷大用足够大的 long long/int64，防止 K、N 较大时累加溢出；dp[j] 不可达要跳过，不能用 0 当初值污染 max。
Code
C++
#include <bits/stdc++.h> using namespace std; /* 把 N 层切成恰好 K 段，最小化「最大段耗时」的线性 DP（滚动数组） */ int main() { ios::sync_with_stdio(false); cin.tie(nullptr); /* 输入共 2N+1 个数：前 N 个是 t，接下来 N 个是 s，最后一个是 K */ vector<long long> v; long long x; while (cin >> x) v.push_back(x); int n = (v.size() - 1) / 2; vector<long long>& t = v; /* t[i] = v[i] */ vector<long long> s(v.begin() + n, v.begin() + 2 * n); int k = (int)v[2 * n]; /* 前缀和 pre[i] = 前 i 层计算耗时之和 */ vector<long long> pre(n + 1, 0); for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + t[i]; /* INF 取足够大，long long 下累加不会溢出 */ const long long INF = 4000000000000000000LL; vector<long long> dp(n + 1, INF), cur(n + 1, INF); dp[0] = 0; /* 边界：0 层切 0 段耗时 0 */ for (int p = 0; p < k; p++) { fill(cur.begin(), cur.end(), INF); for (int i = 1; i <= n; i++) { /* 本段以第 i 层结尾；没盖住最后一层时要加该层通信耗时 */ long long add = (i == n) ? 0 : s[i - 1]; long long best = INF; for (int j = 0; j < i; j++) { if (dp[j] >= INF) continue; /* 前 j 层切不出上一段数 */ long long cost = pre[i] - pre[j] + add; if (dp[j] > cost) cost = dp[j]; /* 与此前最大取较大者 */ if (cost < best) best = cost; } cur[i] = best; } swap(dp, cur); /* 滚动 */ } cout << dp[n] << "\n"; return 0; }Java
import java.util.*; import java.io.*; public class Solution { /* 把 N 层切成恰好 K 段，最小化「最大段耗时」的线性 DP（滚动数组） */ public static void main(String[] args) throws IOException { /* 用 StreamTokenizer 读全部整数，避免 Scanner 在循环里切换读取模式错位 */ StreamTokenizer in = new StreamTokenizer(new BufferedInputStream(System.in)); List<Long> vals = new ArrayList<>(); while (in.nextToken() != StreamTokenizer.TT_EOF) vals.add((long) in.nval); int cnt = vals.size(); int n = (cnt - 1) / 2; long[] t = new long[n]; long[] s = new long[n]; for (int i = 0; i < n; i++) t[i] = vals.get(i); for (int i = 0; i < n; i++) s[i] = vals.get(n + i); int k = (int) (long) vals.get(2 * n); /* 前缀和 pre[i] = 前 i 层计算耗时之和 */ long[] pre = new long[n + 1]; for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + t[i]; /* INF 取足够大且不会因累加溢出 */ final long INF = 4000000000000000000L; long[] dp = new long[n + 1]; long[] cur = new long[n + 1]; Arrays.fill(dp, INF); dp[0] = 0; /* 边界：0 层切 0 段耗时 0 */ for (int p = 0; p < k; p++) { Arrays.fill(cur, INF); for (int i = 1; i <= n; i++) { /* 本段以第 i 层结尾；没盖住最后一层时要加该层通信耗时 */ long add = (i == n) ? 0 : s[i - 1]; long best = INF; for (int j = 0; j < i; j++) { if (dp[j] >= INF) continue; /* 前 j 层切不出上一段数 */ long cost = pre[i] - pre[j] + add; if (dp[j] > cost) cost = dp[j]; /* 与此前最大取较大者 */ if (cost < best) best = cost; } cur[i] = best; } long[] tmp = dp; dp = cur; cur = tmp; /* 滚动 */ } System.out.println(dp[n]); } }Go
package main import ( "bufio" "fmt" "os" ) // 把 N 层切成恰好 K 段，最小化「最大段耗时」的线性 DP（滚动数组） func solve(t, s []int64, k int) int64 { n := len(t) // 前缀和 pre[i] = 前 i 层计算耗时之和 pre := make([]int64, n+1) for i := 0; i < n; i++ { pre[i+1] = pre[i] + t[i] } const INF = int64(4000000000000000000) dp := make([]int64, n+1) cur := make([]int64, n+1) for i := range dp { dp[i] = INF } dp[0] = 0 // 边界：0 层切 0 段耗时 0 for p := 0; p < k; p++ { for i := range cur { cur[i] = INF } for i := 1; i <= n; i++ { // 本段以第 i 层结尾；没盖住最后一层时要加该层通信耗时 add := int64(0) if i != n { add = s[i-1] } best := INF for j := 0; j < i; j++ { if dp[j] >= INF { // 前 j 层切不出上一段数 continue } cost := pre[i] - pre[j] + add if dp[j] > cost { // 与此前最大取较大者 cost = dp[j] } if cost < best { best = cost } } cur[i] = best } dp, cur = cur, dp // 滚动 } return dp[n] } func main() { // bufio.Scanner 默认缓冲区对大输入不够，这里用 Fscan 逐个读 reader := bufio.NewReaderSize(os.Stdin, 1<<20) var vals []int64 for { var x int64 if _, err := fmt.Fscan(reader, &x); err != nil { break } vals = append(vals, x) } cnt := len(vals) n := (cnt - 1) / 2 t := vals[:n] s := vals[n : 2*n] k := int(vals[2*n]) fmt.Println(solve(t, s, k)) }C
#include <stdio.h> #include <stdlib.h> /* 把 N 层切成恰好 K 段，最小化「最大段耗时」的线性 DP（滚动数组） */ int main(void) { /* 一次性读入全部整数：前 N 个是 t，接下来 N 个是 s，最后一个是 K */ long long *v = malloc(2000005 * sizeof(long long)); int cnt = 0; long long x; while (scanf("%lld", &x) == 1) v[cnt++] = x; int n = (cnt - 1) / 2; long long *t = v; /* t[i] = v[i] */ long long *s = v + n; /* s[i] = v[n+i] */ int k = (int)v[2 * n]; /* 前缀和 pre[i] = 前 i 层计算耗时之和 */ long long *pre = malloc((n + 1) * sizeof(long long)); pre[0] = 0; for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + t[i]; /* INF 取足够大，且累加不会溢出 long long */ const long long INF = 4000000000000000000LL; long long *dp = malloc((n + 1) * sizeof(long long)); long long *cur = malloc((n + 1) * sizeof(long long)); for (int i = 0; i <= n; i++) dp[i] = INF; dp[0] = 0; /* 边界：0 层切 0 段耗时 0 */ for (int p = 0; p < k; p++) { for (int i = 0; i <= n; i++) cur[i] = INF; for (int i = 1; i <= n; i++) { /* 本段以第 i 层结尾；没盖住最后一层时要加该层通信耗时 */ long long add = (i == n) ? 0 : s[i - 1]; long long best = INF; for (int j = 0; j < i; j++) { if (dp[j] >= INF) continue; /* 前 j 层切不出上一段数 */ long long cost = pre[i] - pre[j] + add; if (dp[j] > cost) cost = dp[j]; /* 与此前最大取较大者 */ if (cost < best) best = cost; } cur[i] = best; } /* 滚动：cur 变成新的 dp */ long long *tmp = dp; dp = cur; cur = tmp; } printf("%lld\n", dp[n]); free(v); free(pre); free(dp); free(cur); return 0; }Python
import sys def solve(t, s, k): # 计算把 t 数组切成恰好 k 段时「最大段耗时」的最小值 # 参数 t 是各层计算耗时，s 是各层通信耗时，k 是 GPU（段）数 n = len(t) # 前缀和：pre[i] 是前 i 层的计算耗时之和，任意一段耗时 O(1) 得到 pre = [0] * (n + 1) for i in range(n): pre[i + 1] = pre[i] + t[i] inf = float("inf") # dp[i] 表示前 i 层切成当前段数时的最优值，滚动数组省掉第一维 dp = [inf] * (n + 1) dp[0] = 0 for _ in range(k): cur = [inf] * (n + 1) for i in range(1, n + 1): # 本段以第 i 层结尾；没盖住最后一层时要加该层通信耗时 add = 0 if i == n else s[i - 1] best = inf for j in range(i): # 前 j 层切不出上一段数，不能作为本段起点 if dp[j] >= inf: continue # 整体耗时取「前面的最大」与「本段耗时」的较大者 cost = pre[i] - pre[j] + add if dp[j] > cost: cost = dp[j] if cost < best: best = cost cur[i] = best dp = cur return dp[n] def main(): data = sys.stdin.buffer.read().split() vals = list(map(int, data)) # 输入共 2N+1 个数：前 N 个是 t，接下来 N 个是 s，最后一个是 k n = (len(vals) - 1) // 2 t = vals[:n] s = vals[n:2 * n] k = vals[2 * n] print(solve(t, s, k)) main())
