【春招笔试】4月1日阿里系AI算法岗真题解析

四季读书网 2026-04-01 21:22:34 2 0

🔗刷题网址: bishipass.com

27届实习提前批秋招汇总，持续更新，建议收藏，欢迎分享https://docs.qq.com/smartsheet/DRHVEc05MbE5CYUZa?tab=sc_JGxFAj

阿里系列-2026.04.01-算法岗

题目一：K小姐的跨步换位重排

这题最容易误判成“只能做局部调整”。其实位置差为的交换把整个数组拆成了若干条链，同一条链上的元素可以任意重排。明白这一点以后，每组链单独降序，再按原位置放回去，就是字典序最大的答案。

难度：中等

题目二：离观测值最近的质数

数据范围不大，完全没必要上筛法。按距离从小到大往两边试，配上试除判质数，就能把最近答案和同距离取较小值这两个条件一起处理掉。

难度：简单

题目三：二进制日志的定长压缩

这题最容易卡在“压缩段不能重叠”这句。顺着这个限制往下想，会发现每个压缩段都只能待在某个同字符连续段里，所以先把每一段能提供的减少量单独算出来，再做一次总背包合并就够了。

难度：中等

01. K小姐的跨步换位重排

问题描述

说明：阿里系列近期多条业务线笔试题基本共用同一套公开机试，淘天、阿里云等方向都可参考本场。

K小姐在整理一组分散存放的数据块。数组里的元素排在一条长线上，但调度器只允许她做一种固定步长的交换：如果两个位置正好相差，就可以直接对调它们。

现在给定一个长度为的整数数组和一个正整数。你可以进行任意次如下操作：

>
选择一个下标，满足且，将与交换。

请在可以无限次操作的前提下，求出最终能得到的字典序最大的数组。

数组字典序的比较方式如下：从第一个位置开始逐项比较，第一次出现不同的位置上，元素较大的那个数组字典序更大。

输入格式

每个测试文件包含多组测试数据。

>
第一行输入一个整数，表示测试数据组数。
>
对于每组测试数据：

>
第一行输入两个整数。
>
第二行输入个整数。

输出格式

对于每组测试数据，输出一行个整数，表示在这些交换操作下能够得到的字典序最大的数组。

样例输入

3
7 2
1 9 3 8 2 7 4
5 3
10 1 5 9 2
6 6
4 3 2 1 0 -1

样例输出

4 9 3 8 2 7 1
10 2 5 9 1
4 3 2 1 0 -1

数据范围

>
>
>
>
>
所有测试数据中，的总和不超过

样例	解释说明
样例1 第 1 组	位置会按模分成两条链：和。同一条链上的元素可以任意重排，所以把第一条链放成，第二条链保持，得到的整体字典序最大。
样例1 第 2 组	位置按模分成三组：、、。分别把每组里的元素按从大到小放回原位置，答案就是。
样例1 第 3 组	当时，没有任何位置满足，因此数组无法变化。

题解

#先看哪些位置之间真的能互相到达

一次操作只能交换位置差恰好为的两个元素。于是下标会形成若干条独立的链：

>
>
>
...
>

同一条链上的相邻点可以直接交换。因为相邻交换可以生成任意排列，所以同一条链上的元素最终可以任意重排。

而不同链之间永远不会连通，因此元素也不可能跨链移动。

#为什么每条链都要按降序放回

字典序比较最关心前面的位置。

既然位置只能从它所在的那条链里选元素，那么为了让整个数组字典序最大，位置一定要拿到这条链里最大的元素；接下来同理，位置要拿剩下元素里最大的；继续往后都一样。

所以每条链的最优策略就是：

取出这条链上的所有元素。
按从大到小排序。
再按链上的位置顺序依次放回。

把所有链都这样处理完，得到的就是全局字典序最大的数组。

#复杂度分析

每个元素只会被分到一条链里一次，再参与一次排序。

>
时间复杂度：。
>
空间复杂度：。

参考代码

>
Python

import sys
input = lambda: sys.stdin.readline().strip()


defsolve() -> None:
    t = int(input())
    out = []

for _ in range(t):
        n, k = map(int, input().split())
        a = list(map(int, input().split()))
        ans = a[:]

for st in range(k):
            pos = list(range(st, n, k))
            vals = [a[i] for i in pos]

# 同一条链里的元素可以任意重排，按降序放回最优。
            vals.sort(reverse=True)

for i, v in zip(pos, vals):
                ans[i] = v

        out.append(" ".join(map(str, ans)))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

>
Cpp

#include<bits/stdc++.h>
usingnamespacestd;

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;

vector<longlong> a(n), ans(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
            ans[i] = a[i];
        }

for (int st = 0; st < k; ++st) {
vector<int> pos;
vector<longlong> vals;

for (int i = st; i < n; i += k) {
                pos.push_back(i);
                vals.push_back(a[i]);
            }

// 这条链上的元素可任意重排，降序放回即可让前面的位置尽量大。
            sort(vals.begin(), vals.end(), greater<longlong>());

for (int i = 0; i < (int) pos.size(); ++i) {
                ans[pos[i]] = vals[i];
            }
        }

for (int i = 0; i < n; ++i) {
if (i) {
cout << ' ';
            }
cout << ans[i];
        }
cout << '\n';
    }
return0;
}

>
Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

publicclassMain{
staticclassFastScanner{
privatefinal BufferedInputStream in = new BufferedInputStream(System.in);
privatefinalbyte[] buf = newbyte[1 << 16];
privateint len = 0;
privateint ptr = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

intnextInt()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

int sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

int val = 0;
while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
return val * sign;
        }

longnextLong()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

long sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

long val = 0;
while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
return val * sign;
        }
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

int T = fs.nextInt();
while (T-- > 0) {
int n = fs.nextInt();
int k = fs.nextInt();

long[] a = newlong[n];
long[] ans = newlong[n];
for (int i = 0; i < n; ++i) {
                a[i] = fs.nextLong();
                ans[i] = a[i];
            }

for (int st = 0; st < k; ++st) {
                ArrayList<Integer> pos = new ArrayList<>();
                ArrayList<Long> vals = new ArrayList<>();

for (int i = st; i < n; i += k) {
                    pos.add(i);
                    vals.add(a[i]);
                }

// 同链元素能任意排列，所以直接按降序放回。
                vals.sort(Collections.reverseOrder());

for (int i = 0; i < pos.size(); ++i) {
                    ans[pos.get(i)] = vals.get(i);
                }
            }

for (int i = 0; i < n; ++i) {
if (i > 0) {
                    out.append(' ');
                }
                out.append(ans[i]);
            }
            out.append('\n');
        }

        System.out.print(out);
    }
}

02. 离观测值最近的质数

问题描述

卢小姐在调试一台会产生整数读数的采样器。某次读数记成了整数，她想把这个值校准到离它最近的质数上，作为后续实验的标准刻度。

也就是说，她需要找出一个质数，使得尽可能小。

如果有两个质数到的距离相同，那么输出较小的那个。

输入格式

每个测试文件包含多组测试数据。

>
第一行输入一个整数，表示测试数据组数。
>
接下来行，每行输入一个整数。

输出格式

对于每组测试数据，输出一行一个整数，表示与距离最近的质数。

样例输入

样例输出

数据范围

样例	解释说明
样例1	当时，最近的两个质数是和，距离都为，因此要输出更小的。

题解

#直接按距离向两边找

如果当前距离是，那么离距离正好为的候选数只有两个：

因为题目要求：

先让距离最小。
若距离相同，取更小的那个。

所以最自然的做法就是从开始往外扩：

先检查是否是质数。
如果不是，再检查是否是质数。
一旦找到答案，立刻输出。

这样第一次找到的质数，一定就是最近的；而且同距离时总是先检查较小的那个，也正好满足题目的次级要求。

#质数判定怎么做

因为，并且测试数据最多只有组，没有必要做复杂预处理。

对于一个数：

>
若，它不是质数。
>
若能被或整除，就只有和本身是质数。
>
再往后只需要检查形如的因子，直到为止。

这个试除复杂度已经完全够用。

#复杂度分析

设最终答案距离输入值的距离是。

>
每次候选判质的复杂度是。
>
总共大约会检查个候选值。

在本题数据范围下，这个复杂度足够通过。

参考代码

>
Python

import sys
input = lambda: sys.stdin.readline().strip()


defis_prime(x: int) -> bool:
if x < 2:
returnFalse
# 先单独处理最小的两个质因子。
if x % 2 == 0:
return x == 2
if x % 3 == 0:
return x == 3

# 之后只需要检查 6k±1 这两类候选因子。
    d = 5
while d * d <= x:
if x % d == 0or x % (d + 2) == 0:
returnFalse
        d += 6
returnTrue


defsolve() -> None:
    t = int(input())
    out = []

for _ in range(t):
        x = int(input())
        d = 0

whileTrue:
            y = x - d
# 同距离时要优先返回更小的那个，所以先检查 x-d。
if y >= 2and is_prime(y):
                out.append(str(y))
break

if d > 0:
                z = x + d
# 只有较小端没命中时，才检查较大端。
if is_prime(z):
                    out.append(str(z))
break

            d += 1

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

>
Cpp

#include<bits/stdc++.h>
usingnamespacestd;

boolis_prime(int x){
if (x < 2) {
returnfalse;
    }
// 先特判最小的两个质因子。
if (x % 2 == 0) {
return x == 2;
    }
if (x % 3 == 0) {
return x == 3;
    }

// 之后只检查 6k±1 形式的因子即可。
for (longlong d = 5; d * d <= x; d += 6) {
if (x % d == 0 || x % (d + 2) == 0) {
returnfalse;
        }
    }
returntrue;
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
int x;
cin >> x;

for (int d = 0;; ++d) {
int y = x - d;
// 同距离时优先取更小的答案，所以先查左边。
if (y >= 2 && is_prime(y)) {
cout << y << '\n';
break;
            }

if (d > 0) {
int z = x + d;
// 左边没命中时，再检查右边。
if (is_prime(z)) {
cout << z << '\n';
break;
                }
            }
        }
    }
return0;
}

>
Java

import java.io.BufferedInputStream;
import java.io.IOException;

publicclassMain{
staticclassFastScanner{
privatefinal BufferedInputStream in = new BufferedInputStream(System.in);
privatefinalbyte[] buf = newbyte[1 << 16];
privateint len = 0;
privateint ptr = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

intnextInt()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

int sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

int val = 0;
while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
return val * sign;
        }
    }

staticbooleanisPrime(int x){
if (x < 2) {
returnfalse;
        }
// 先把最小的两个质因子单独处理掉。
if (x % 2 == 0) {
return x == 2;
        }
if (x % 3 == 0) {
return x == 3;
        }

// 接下来只需要枚举 6k±1 这两类可能的因子。
for (long d = 5; d * d <= x; d += 6) {
if (x % d == 0 || x % (d + 2) == 0) {
returnfalse;
            }
        }
returntrue;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

int T = fs.nextInt();
while (T-- > 0) {
int x = fs.nextInt();

for (int d = 0; ; ++d) {
int y = x - d;
// 同距离时先看较小的那个候选值。
if (y >= 2 && isPrime(y)) {
                    out.append(y).append('\n');
break;
                }

if (d > 0) {
int z = x + d;
// 左边没找到时，再检查右边。
if (isPrime(z)) {
                        out.append(z).append('\n');
break;
                    }
                }
            }
        }

        System.out.print(out);
    }
}

03. 二进制日志的定长压缩

问题描述

K小姐在做一套二进制日志归档工具。原始日志只包含字符 0 和 1，但系统允许把一整段相同字符折叠成一个“压缩标记”，以便把总长度压到指定范围内。

现在她拿到了一段长度为的日志串，并且可以对它执行若干次压缩操作。

一次压缩操作需要满足：

>
选择一个连续子串，并且这个子串里的字符全都相同。
>
设这个子串长度为，必须满足。
>
把这一整段压缩成一个新的特殊字符。这个特殊字符的长度视为，并且它不再属于 0 或 1。
>
如果这次压缩的段长为，那么代价是。

除此之外，还需要满足：

>
不同压缩段之间不能重叠。
>
已经被压缩过的部分，后续不能再次参与压缩。

压缩完成后，字符串的新长度等于：

>
所有未被压缩的原字符个数。
>
再加上所有压缩段变成的特殊字符个数。

现在给定目标长度。请把原字符串压缩到恰好长度为，并让总代价最小。

如果无法做到，输出 -1。

输入格式

每个测试文件包含多组测试数据。

>
第一行输入一个整数，表示测试数据组数。
>
对于每组测试数据：

>
第一行输入两个整数。
>
第二行输入一个长度为的二进制字符串。
>
第三行输入个整数，其中表示压缩长度为的同字符连续段所需的代价。

输出格式

对于每组测试数据，输出一个整数，表示把字符串长度压缩到恰好的最小总代价。

如果无法达到长度，输出 -1。

样例输入

3
6 4
001110
1 5 4 20 20 20
5 2
01010
1 3 6 10 15
7 4
1111000
1 2 5 10 20 30 40

样例输出

4
-1
6

数据范围

>
>
>
>
>
所有测试数据的之和不超过

样例	解释说明
样例1 第 1 组	串 `001110` 里可以直接压缩中间的 `111`，长度从变成，总长度正好减少，代价是。
样例1 第 2 组	串 `01010` 没有任何长度至少为的同字符连续段，因此无法做任何压缩，也就不可能把长度从变成。
样例1 第 3 组	可以把 `1111` 切成两段 `11`，再把 `000` 里拿一段 `00` 压缩，三次都花费，总长度减少，总代价是。

题解

#先把字符串拆成连续段

压缩时要求选中的子串里所有字符都相同，所以一个压缩段一定完全落在某个连续段内部。

例如：

>
001110 会拆成长度为的三段。

不同连续段之间互不影响，因此可以先分别计算“每一段最多能提供多少长度减少量，以及对应的最小代价”，最后再把这些结果合并。

#单个连续段怎么做

设当前连续段长度为。

这一段里的每个字符最终只有两种去向：

保持原样，作为一个长度为的普通字符。
和同段内若干相邻字符一起，被压缩成一个特殊字符。

于是可以把这一段看成“把长度为的线段切成若干块”：

>
切出长度为的块，表示这一位不压缩，代价为。
>
切出长度为的块，表示把这一整块压缩，代价为。

如果最终一共切成了块，那么压缩后的这整段长度就是，原长是，所以这段提供的长度减少量就是：

因此可以做一个段内动态规划：

>
dp[used][cnt] 表示已经覆盖了前 used 个字符，并且一共切出了 cnt 块时的最小代价。

枚举下一块的长度即可。

最后对所有 cnt 取值，把：

对应的最小代价记下来，得到这一个连续段的“局部答案表”。

#再把所有连续段合并

设总共需要把长度从压到，也就是需要总减少：

对于每个连续段，已经知道它能提供各种减少量的最小代价。接下来再做一次总背包：

>
f[x] 表示处理完前若干段后，恰好总共减少了 x 个长度的最小代价。

按连续段逐个转移即可。

如果最终 f[need] 仍然不存在，说明无法恰好压到长度，输出 -1。

#复杂度分析

设某个连续段长度为。

>
这段内部的切分 DP 复杂度约为。
>
由于所有测试数据的总长度不超过，这个做法可以接受。
>
总背包部分复杂度为。

参考代码

>
Python

import sys
input = lambda: sys.stdin.readline().strip()

INF = 10**30


defbuild_cost(length: int, cost: list[int]) -> list[int]:
# dp[used][cnt]：前 used 个字符被切成 cnt 块时的最小代价。
    dp = [[INF] * (length + 1) for _ in range(length + 1)]
    dp[0][0] = 0

for used in range(length):
        rem = length - used
for cnt in range(used + 1):
            cur = dp[used][cnt]
if cur == INF:
continue

# 下一块长度为 1，表示这个字符保持原样。
if cur < dp[used + 1][cnt + 1]:
                dp[used + 1][cnt + 1] = cur

# 下一块长度至少为 2，表示整块压缩。
for k in range(2, rem + 1):
                val = cur + cost[k]
if val < dp[used + k][cnt + 1]:
                    dp[used + k][cnt + 1] = val

    best = [INF] * length
for cnt in range(1, length + 1):
        red = length - cnt
if dp[length][cnt] < best[red]:
            best[red] = dp[length][cnt]
return best


defsolve() -> None:
    t = int(input())
    out = []

for _ in range(t):
        n, m = map(int, input().split())
        s = input()
        a = [0] + list(map(int, input().split()))
        need = n - m

if need == 0:
            out.append("0")
continue

        runs = []
        i = 0
while i < n:
            j = i
while j < n and s[j] == s[i]:
                j += 1
            runs.append(j - i)
            i = j

        max_reduce = sum(x - 1for x in runs)
if need > max_reduce:
            out.append("-1")
continue

        dp = [INF] * (need + 1)
        dp[0] = 0

for length in runs:
            best = build_cost(length, a)
            ndp = [INF] * (need + 1)

for now in range(need + 1):
if dp[now] == INF:
continue

                lim = min(length - 1, need - now)
for red in range(lim + 1):
                    val = dp[now] + best[red]
if val < ndp[now + red]:
                        ndp[now + red] = val

            dp = ndp

        out.append(str(dp[need] if dp[need] < INF else-1))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    solve()

>
Cpp

#include<bits/stdc++.h>
usingnamespacestd;

using ll = longlong;
staticconstlonglong INF = (1LL << 62);

vector<ll> build_cost(int len, constvector<ll>& a){
vector<vector<ll>> dp(len + 1, vector<ll>(len + 1, INF));
    dp[0][0] = 0;

for (int used = 0; used < len; ++used) {
int rem = len - used;
for (int cnt = 0; cnt <= used; ++cnt) {
            ll cur = dp[used][cnt];
if (cur == INF) {
continue;
            }

// 长度为 1 的块不压缩。
            dp[used + 1][cnt + 1] = min(dp[used + 1][cnt + 1], cur);

// 长度至少为 2 的块整体压缩。
for (int k = 2; k <= rem; ++k) {
                dp[used + k][cnt + 1] = min(dp[used + k][cnt + 1], cur + a[k]);
            }
        }
    }

vector<ll> best(len, INF);
for (int cnt = 1; cnt <= len; ++cnt) {
int red = len - cnt;
        best[red] = min(best[red], dp[len][cnt]);
    }
return best;
}

intmain(){
    ios::sync_with_stdio(false);
cin.tie(nullptr);

int T;
cin >> T;
while (T--) {
int n, m;
cin >> n >> m;
string s;
cin >> s;

vector<ll> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
        }

int need = n - m;
if (need == 0) {
cout << 0 << '\n';
continue;
        }

vector<int> runs;
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s[j] == s[i]) {
                ++j;
            }
            runs.push_back(j - i);
            i = j;
        }

int max_reduce = 0;
for (int len : runs) {
            max_reduce += len - 1;
        }
if (need > max_reduce) {
cout << -1 << '\n';
continue;
        }

vector<ll> dp(need + 1, INF);
        dp[0] = 0;

for (int len : runs) {
vector<ll> best = build_cost(len, a);
vector<ll> ndp(need + 1, INF);

for (int now = 0; now <= need; ++now) {
if (dp[now] == INF) {
continue;
                }

int lim = min(len - 1, need - now);
for (int red = 0; red <= lim; ++red) {
                    ndp[now + red] = min(ndp[now + red], dp[now] + best[red]);
                }
            }

            dp.swap(ndp);
        }

cout << (dp[need] == INF ? -1 : dp[need]) << '\n';
    }
return0;
}

>
Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;

publicclassMain{
staticfinallong INF = Long.MAX_VALUE / 4;

staticclassFastScanner{
privatefinal BufferedInputStream in = new BufferedInputStream(System.in);
privatefinalbyte[] buf = newbyte[1 << 16];
privateint len = 0;
privateint ptr = 0;

privateintread()throws IOException {
if (ptr >= len) {
                len = in.read(buf);
                ptr = 0;
if (len <= 0) {
return -1;
                }
            }
return buf[ptr++];
        }

intnextInt()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

int sign = 1;
if (c == '-') {
                sign = -1;
                c = read();
            }

int val = 0;
while (c > ' ') {
                val = val * 10 + c - '0';
                c = read();
            }
return val * sign;
        }

String next()throws IOException {
int c;
do {
                c = read();
            } while (c <= ' ' && c != -1);

            StringBuilder sb = new StringBuilder();
while (c > ' ') {
                sb.append((char) c);
                c = read();
            }
return sb.toString();
        }
    }

staticlong[] buildCost(int len, long[] a) {
long[][] dp = newlong[len + 1][len + 1];
for (int i = 0; i <= len; ++i) {
for (int j = 0; j <= len; ++j) {
                dp[i][j] = INF;
            }
        }
        dp[0][0] = 0;

for (int used = 0; used < len; ++used) {
int rem = len - used;
for (int cnt = 0; cnt <= used; ++cnt) {
long cur = dp[used][cnt];
if (cur == INF) {
continue;
                }

// 长度为 1 的块保持原样。
if (cur < dp[used + 1][cnt + 1]) {
                    dp[used + 1][cnt + 1] = cur;
                }

// 长度至少为 2 的块整体压缩。
for (int k = 2; k <= rem; ++k) {
long val = cur + a[k];
if (val < dp[used + k][cnt + 1]) {
                        dp[used + k][cnt + 1] = val;
                    }
                }
            }
        }

long[] best = newlong[len];
for (int i = 0; i < len; ++i) {
            best[i] = INF;
        }
for (int cnt = 1; cnt <= len; ++cnt) {
int red = len - cnt;
if (dp[len][cnt] < best[red]) {
                best[red] = dp[len][cnt];
            }
        }
return best;
    }

publicstaticvoidmain(String[] args)throws Exception {
        FastScanner fs = new FastScanner();
        StringBuilder out = new StringBuilder();

int T = fs.nextInt();
while (T-- > 0) {
int n = fs.nextInt();
int m = fs.nextInt();
            String s = fs.next();

long[] a = newlong[n + 1];
for (int i = 1; i <= n; ++i) {
                a[i] = fs.nextInt();
            }

int need = n - m;
if (need == 0) {
                out.append(0).append('\n');
continue;
            }

            ArrayList<Integer> runs = new ArrayList<>();
for (int i = 0; i < n; ) {
int j = i;
while (j < n && s.charAt(j) == s.charAt(i)) {
                    j++;
                }
                runs.add(j - i);
                i = j;
            }

int maxReduce = 0;
for (int len : runs) {
                maxReduce += len - 1;
            }
if (need > maxReduce) {
                out.append(-1).append('\n');
continue;
            }

long[] dp = newlong[need + 1];
for (int i = 0; i <= need; ++i) {
                dp[i] = INF;
            }
            dp[0] = 0;

for (int len : runs) {
long[] best = buildCost(len, a);
long[] ndp = newlong[need + 1];
for (int i = 0; i <= need; ++i) {
                    ndp[i] = INF;
                }

for (int now = 0; now <= need; ++now) {
if (dp[now] == INF) {
continue;
                    }

int lim = Math.min(len - 1, need - now);
for (int red = 0; red <= lim; ++red) {
long val = dp[now] + best[red];
if (val < ndp[now + red]) {
                            ndp[now + red] = val;
                        }
                    }
                }

                dp = ndp;
            }

            out.append(dp[need] == INF ? -1 : dp[need]).append('\n');
        }

        System.out.print(out);
    }
}