题解：

问题定义

我们有一个“好序列”的定义：

1. 序列的第一个元素必须是 1
2. 对于每个位置 j > 1，要么：
   • x_j = x_{j-1} + 1（加法操作）
   • x_j = x_k × x_l，其中 0 < k ≤ l < j（乘法操作）

所有序列元素必须满足 1 ≤ x_j ≤ n。

给定权重 w_1, ..., w_n，序列的权重是所有元素对应权重之和。

对于每个 v ∈ [1, n]，定义 s_v 为包含 v 的好序列的最小权重。

关键观察

1. 序列必须从 1 开始：这意味着所有好序列都包含 1
2. 两种扩展方式：
   • 加法：从 u 到 u+1，代价 w_{u+1}
   • 乘法：从已有的 u 和 v 得到 u×v，代价 w_{u×v}
3. s_v 的含义：从 1 到达 v 的最小总权重路径

图论建模

我们可以将这个问题建模为最短路径问题：

• 节点：1 到 n 的整数
• 初始距离：dist[1] = w_1
• 边：
  • 加法边：u → u+1，权重 w_{u+1}
  • 乘法边：当 u 和 v 都可达时，可以到达 u×v，权重 w_{u×v}

算法选择

使用 Dijkstra 算法，因为所有权重 w_i ≥ 1，保证非负。

关键优化：

• 对于乘法操作，当节点 u 出队时，枚举所有已访问的节点 i，更新 u×i
• 为了效率，可以限制 i ≤ u 且 u×i ≤ n

时间复杂度

• 每个节点出队一次：O(n log n)
• 每个节点 u 处理时枚举 i：O(n/u)（调和级数）
• 总复杂度：O(n log n)

C 语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 30005
#define INF (1LL << 60)

typedef long long ll;

int n;
ll w[MAXN];
ll dist[MAXN];
int visited[MAXN];

// 最小堆实现
typedef struct {
    ll dist;
    int val;
} Node;

Node heap[MAXN * 2];
int heapSize;

void push(ll d, int v) {
    int i = ++heapSize;
    while (i > 1 && heap[i / 2].dist > d) {
        heap[i] = heap[i / 2];
        i /= 2;
    }
    heap[i].dist = d;
    heap[i].val = v;
}

int isEmpty() {
    return heapSize == 0;
}

Node pop() {
    Node ret = heap[1];
    Node last = heap[heapSize--];
    int i = 1;
    while (i * 2 <= heapSize) {
        int child = i * 2;
        if (child + 1 <= heapSize && heap[child + 1].dist < heap[child].dist)
            child++;
        if (last.dist <= heap[child].dist) break;
        heap[i] = heap[child];
        i = child;
    }
    heap[i] = last;
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &w[i]);
        dist[i] = INF;
    }

    // 初始化
    dist[1] = w[1];
    push(w[1], 1);

    // Dijkstra 算法
    while (!isEmpty()) {
        Node node = pop();
        int u = node.val;
        
        if (visited[u]) continue;
        visited[u] = 1;

        // 加法操作：u -> u+1
        if (u < n) {
            ll new_dist = dist[u] + w[u + 1];
            if (new_dist < dist[u + 1]) {
                dist[u + 1] = new_dist;
                push(new_dist, u + 1);
            }
        }

        // 乘法操作：u 和 i -> u*i
        // 优化：只枚举 i <= u 避免重复
        for (int i = 1; i <= u && (ll)u * i <= n; i++) {
            if (!visited[i]) continue;
            
            int target = u * i;
            ll new_dist = dist[u] + dist[i] + w[target];
            
            if (new_dist < dist[target]) {
                dist[target] = new_dist;
                push(new_dist, target);
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= n; i++) {
        printf("%lld\n", dist[i]);
    }

    return 0;
}

样例验证

输入：

3
10
42
1

运行过程：

1. dist[1] = 10
2. 从 1 出发：
   • 加法：1→2，dist[2] = 10+42 = 52
   • 乘法：1×1=1（无意义）
3. 从 2 出发：
   • 加法：2→3，dist[3] = 52+1 = 53
   • 乘法：2×1=2（已访问），2×2=4（超出范围）

输出：

10
52
53

与题目样例一致。

算法正确性证明

1. 最优子结构：到达任何数字 v 的最小权重路径，其前缀也是最优的
2. 无负权：所有权重 w_i ≥ 1，Dijkstra 算法适用
3. 覆盖所有操作：
   • 加法操作通过 u → u+1 边覆盖
   • 乘法操作通过检查所有已访问节点对覆盖
4. 终止条件：所有 1..n 的数字都被访问或确定不可达

复杂度分析

• 时间复杂度：O(n log n)
  • 每个节点入队出队一次：O(n log n)
  • 乘法操作枚举：∑(n/i) ≈ O(n log n)
• 空间复杂度：O(n)

总结

本题的关键在于将序列生成问题转化为图的最短路径问题，通过 Dijkstra 算法高效求解。乘法操作的优化枚举是保证算法效率的核心。

该解法可以处理 n ≤ 3×10^4 的数据规模，在所有测试用例上都能高效运行。