T2-1 四大宝石的共鸣

思路（4 层 DP）

设砖块数组为 B[0..N-1]，要选下标严格递增的 i0<i1<i2<i3，最大化：

A0*B[i0] + A1*B[i1] + A2*B[i2] + A3*B[i3]

做递推：

• dp0[i]：只选 1 块，且最后一块选在 i 的最大分

  dp0[i] = A0*B[i]

• dp1[i]：选 2 块，且第二块选在 i

  dp1[i] = max_{j<i}(dp0[j]) + A1*B[i]

• dp2[i]：选 3 块，且第三块选在 i

  dp2[i] = max_{j<i}(dp1[j]) + A2*B[i]

• dp3[i]：选 4 块，且第四块选在 i

  dp3[i] = max_{j<i}(dp2[j]) + A3*B[i]

关键是维护前缀最大值：

best0 = max(dp0[0..i-1])，best1，best2，一路扫一遍就行。

注意：

• Ai, Bi 可能为负，所以初始必须是 -INF，不能用 0（样例2会错）。
• 用 long long。

---

参考代码

#include <bits/stdc++.h>
using namespace std;

// 只把大数组放全局（避免栈空间不够）
long long B[100000 + 5];                 // 砖块能量值数组

int main() {
    long long A[4];                      
    int N;                               
    long long NEG = -(1LL << 62);        

    for (int i = 0; i < 4; i++)          // 读入 A0..A3
        cin >> A[i];

    cin >> N;                            // 读入 N

    for (int i = 0; i < N; i++)          // 读入 B0..B{N-1}
        cin >> B[i];

    long long best0 = NEG;               // 前缀最优：选第1块的最大值
    long long best1 = NEG;               // 前缀最优：选到第2块的最大值
    long long best2 = NEG;               // 前缀最优：选到第3块的最大值
    long long ans  = NEG;                // 最终答案：选到第4块的最大值

    for (int i = 0; i < N; i++) {        // 枚举当前位置 i 作为“某层选择的最后一块”
        long long dp0 = A[0] * B[i];     // 只选 1 块，且选在 i：A0 * B[i]

        // 选 2 块，且第 2 块选在 i：max(dp0[0..i-1]) + A1*B[i]
        long long dp1 = (best0 == NEG ? NEG : best0 + A[1] * B[i]);

        // 选 3 块，且第 3 块选在 i：max(dp1[0..i-1]) + A2*B[i]
        long long dp2 = (best1 == NEG ? NEG : best1 + A[2] * B[i]);

        // 选 4 块，且第 4 块选在 i：max(dp2[0..i-1]) + A3*B[i]
        long long dp3 = (best2 == NEG ? NEG : best2 + A[3] * B[i]);

        best0 = max(best0, dp0);         // 更新前缀最优
        best1 = max(best1, dp1);         // 更新前缀最优
        best2 = max(best2, dp2);         // 更新前缀最优

        ans = max(ans, dp3);             // 更新答案：所有 dp3 取最大
    }

    cout << ans << endl;                 // 输出最大总分
    return 0;                            // 结束
}