#P4569. 第3题-AIGC缓存复用加速策略
-
1000ms
Tried: 6
Accepted: 2
Difficulty: 8
所属公司 :
华为
时间 :2026年2月4日-AI方向
-
算法标签>动态规划
第3题-AIGC缓存复用加速策略
解题思路
题意可抽象为:共有 T 次迭代(编号 0∼T−1)。当跳过第 t+1 步(0≤t<T−1)时,相当于复用第 t 步的计算结果,会产生损失值 loss[t]。因此一共有 T−1 个“可跳过的位置”(对应步骤 1∼T−1),每个位置选中则付出相应损失。
要求:恰好跳过 k 步,且不能连续跳过两步(即所选位置不能相邻),使总损失最小;若无解输出 −1。
这是典型的“带相邻限制的选取最小代价”问题,使用动态规划(DP):
-
设 n=T−1,位置 i=1∼n 对应损失代价 ci=loss[i−1]。
-
令 dp[i][j][s] 表示考虑前 i 个位置,已经跳过 j 次,且第 i 个位置是否跳过(s∈0,1)时的最小总损失。
- s=0:第 i 个位置不跳过
- s=1:第 i 个位置跳过
状态转移:
- 不跳过第 i 个位置:dp[i][j][0]=min(dp[i−1][j][0], dp[i−1][j][1])
- 跳过第 i 个位置(则第 i−1 个位置不能跳过):dp[i][j][1]=dp[i−1][j−1][0]+ci
初始化:
- dp[0][0][0]=0,其余为无穷大。
答案:
- min(dp[n][k][0], dp[n][k][1]),若仍为无穷大则输出 −1。
复杂度分析
设 n=T−1。
- 时间复杂度:O(nk),因为每个 i,j 只做常数次转移。
- 空间复杂度:O(nk)(也可用滚动数组优化到 O(k),但本题 T≤1000,nk≤106 规模可接受)。
代码实现
import sys
INF = 10**18
def min_total_loss(T, k, loss):
"""
返回在不允许连续跳过的条件下,恰好跳过k步的最小总损失;无解返回-1
"""
n = T - 1 # 可跳过的位置数量
if k < 0 or k > n:
return -1
# dp[i][j][0/1]
dp = [[[INF, INF] for _ in range(k + 1)] for _ in range(n + 1)]
dp[0][0][0] = 0
for i in range(1, n + 1):
cost = loss[i - 1] # 位置i对应的损失
for j in range(0, k + 1):
# 不跳过位置i
dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1])
# 跳过位置i:上一位置必须不跳过,且j>=1
if j >= 1 and dp[i - 1][j - 1][0] != INF:
dp[i][j][1] = dp[i - 1][j - 1][0] + cost
ans = min(dp[n][k][0], dp[n][k][1])
return -1 if ans >= INF else ans
def main():
data = sys.stdin.read().strip().split()
if not data:
return
T = int(data[0])
k = int(data[1])
# 题面保证是T-1个正整数;直接按token读取
loss = list(map(int, data[2:2 + (T - 1)]))
print(min_total_loss(T, k, loss))
if __name__ == "__main__":
main()
#include <bits/stdc++.h>
using namespace std;
static const long long INF = (long long)4e18;
// 返回最小总损失;无解返回-1
long long minTotalLoss(int T, int k, const vector<int>& loss) {
int n = T - 1; // 可跳过的位置数
if (k < 0 || k > n) return -1;
// dp[i][j][0/1]
vector<vector<array<long long, 2>>> dp(n + 1, vector<array<long long, 2>>(k + 1, {INF, INF}));
dp[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
long long cost = loss[i - 1]; // 位置i的损失
for (int j = 0; j <= k; j++) {
// 不跳过位置i
dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1]);
// 跳过位置i:上一位置必须不跳过
if (j >= 1 && dp[i - 1][j - 1][0] < INF) {
dp[i][j][1] = dp[i - 1][j - 1][0] + cost;
}
}
}
long long ans = min(dp[n][k][0], dp[n][k][1]);
return ans >= INF ? -1 : ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T, k;
cin >> T >> k;
int n = T - 1;
vector<int> loss(n);
for (int i = 0; i < n; i++) cin >> loss[i];
cout << minTotalLoss(T, k, loss) << "\n";
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final long INF = (long) 4e18;
// 返回最小总损失;无解返回-1
public static long minTotalLoss(int T, int k, int[] loss) {
int n = T - 1; // 可跳过的位置数
if (k < 0 || k > n) return -1;
// dp[i][j][0/1]
long[][][] dp = new long[n + 1][k + 1][2];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j][0] = INF;
dp[i][j][1] = INF;
}
}
dp[0][0][0] = 0;
for (int i = 1; i <= n; i++) {
long cost = loss[i - 1]; // 位置i的损失
for (int j = 0; j <= k; j++) {
// 不跳过位置i
dp[i][j][0] = Math.min(dp[i - 1][j][0], dp[i - 1][j][1]);
// 跳过位置i:上一位置必须不跳过
if (j >= 1 && dp[i - 1][j - 1][0] < INF) {
dp[i][j][1] = dp[i - 1][j - 1][0] + cost;
}
}
}
long ans = Math.min(dp[n][k][0], dp[n][k][1]);
return ans >= INF ? -1 : ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String line;
while ((line = br.readLine()) != null) {
line = line.trim();
if (!line.isEmpty()) sb.append(line).append(" ");
}
StringTokenizer st = new StringTokenizer(sb.toString());
if (!st.hasMoreTokens()) return;
int T = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int n = T - 1;
int[] loss = new int[n];
for (int i = 0; i < n; i++) {
loss[i] = Integer.parseInt(st.nextToken());
}
System.out.println(minTotalLoss(T, k, loss));
}
}
题目内容
Stable/Diffusion为代表的图像和视频生成模型采用了一种逐步优化的方法:模型会多次迭代运行同一个核心算法,将初始的随机噪声逐步优化成清晰的图像或视频。随着对生成质量和视频时长要求的提高,核心算法的迭代步骤数持续增大,导致该方法的计算量急剧增加(计算量与步骤数成正比),造成应用部署困难。
为了降低计算负载,可以采用 “缓存复用” 策略:研究发现,相邻步骤的特征往往相似,当第 t 步和第t+1步的特征高度相似时,我们可以直接复用第t 步的计算结果,跳过第t+1 步的计算。对于总共 T步的优化过程,如果跳过 k步,计算量就能降低为原来的(T−k)/T。
然而,跳过步骤会带来图像和视频生成质量的损失。用一个长度为 T−1 的损失值列表来记录跳过每一个步骤所带来的损失:列表中的第t 个元素(0≤t<T)表示在第t+1 步时复用第t步的计算结果(即跳过第t+1步计算)所导致的损失值。为了保证生成质量,不能连续跳过2 个及以上步骤(即不能连续复用)。请设计一个函数,在给定总迭代步骤数T、需要跳过的步骤数k,以及损失值列表的情况下,寻找最优的跳过策略,输出最小的总损失值。
输入描述
- T:正整数 T,表示总迭代步骤数(1<T≤1000)。
- k:正整数 k,表示需要跳过的步骤数(0≤k<T)。
- loss:损失值列表,以空格分隔的T−1 个正整数。第 t个值(0≤t<T)表示跳过第 t+1步(复用第t 步的计算结果)所带来的损失值。每个损失值均为小于 1000 的正整数。
输出描述
output: 如果没有找到合适的解,输出 −1;否则输出最小的总损失值。
样例 1
输入
6
2
2 1 2 4 5
输出
4
说明
跳过第 1 个步骤和第3个步骤,总损失值为 2+2=4。由于不能连续跳过2 个步骤,因此不能跳过步骤1和步骤2,或跳过步骤2 和步骤 3。
样例 2
输入
6
4
2 1 2 4 5
输出
-1
说明
总迭代步骤数为5 时,无法跳过 4 个不连续的步骤,因此返回−1。