Bài T1 – Tổng lũy thừa bậc bốn tối đa
Cho dãy gồm n số nguyên dương a[0], a[1], ..., a[n−1]. Bạn được phép chọn một tập con (mỗi phần tử chọn tối đa một lần) sao cho tổng giá trị các phần tử được chọn không vượt quá m. Mục tiêu là cực đại hóa tổng các giá trị a[i]4 của các phần tử đã chọn.

Ràng buộc:
• 1 ≤ n ≤ 4000
• 1 ≤ m ≤ 10⁴
• 1 ≤ a[i] ≤ 10⁴

Đây là bài toán balo 0–1 cổ điển với trọng lượng là giá trị phần tử và giá trị là lũy thừa bậc bốn của nó. Do giới hạn bộ nhớ, ta áp dụng tối ưu không gian bằng mảng một chiều. Với mỗi phần tử v = a[i], cập nhật ngược từ cap = m xuống v để đảm bảo mỗi phần tử chỉ được dùng một lần.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n, capacity;
    cin >> n >> capacity;

    vector<int> values(n);
    for (int i = 0; i < n; ++i) {
        cin >> values[i];
    }

    vector<long long> dp(capacity + 1, 0);
    for (int i = 0; i < n; ++i) {
        int v = values[i];
        long long power4 = 1LL * v * v * v * v;
        for (int cap = capacity; cap >= v; --cap) {
            dp[cap] = max(dp[cap], dp[cap - v] + power4);
        }
    }

    cout << dp[capacity] << '\n';
    return 0;
}

Bài T2 – Chuỗi hạt năng lượng tối ưu
Có n hạt năng lượng, mỗi hạt có kích thước size[i]. Khi nối hai hạt liên tiếp có kích thước x và y, hệ thống sinh ra năng lượng bằng x * y. Các hạt được nối theo thứ tự chỉ số tăng dần (tức là nếu chọn các chỉ số i₁ < i₂ < ... < iₖ, thì năng lượng thu được là size[i₁]×size[i₂] + size[i₂]×size[i₃] + ...). Tổng kích thước các hạt được chọn không được vượt quá m. Hãy tìm giá trị năng lượng lớn nhất có thể đạt được.

Ràng buộc:
• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 5000
• 1 ≤ size[i] ≤ 1000

Do thứ tự chọn bị ràng buộc bởi chỉ số, ta định nghĩa trạng thái: dp[i][w] là năng lượng tối đa khi kết thúc bằng hạt thứ i và tổng kích thước của toàn bộ chuỗi không vượt quá w. Với mỗi cặp (i, w), ta duyệt tất cả các vị trí j < i sao cho w ≥ size[i] + size[j], và cập nhật:
dp[i][w] = max(dp[i][w], dp[j][w − size[i]] + size[j] * size[i]).

Giá trị đáp án là giá trị lớn nhất trong toàn bộ mảng dp[0..n−1][m].

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n, max_weight;
    cin >> n >> max_weight;

    vector<int> sizes(n);
    for (int i = 0; i < n; ++i) {
        cin >> sizes[i];
    }

    // dp[i][w]: max energy ending at index i with total weight ≤ w
    vector<vector<int>> dp(n, vector<int>(max_weight + 1, 0));

    for (int i = 0; i < n; ++i) {
        int s_i = sizes[i];
        for (int w = s_i; w <= max_weight; ++w) {
            // Try to extend from any previous bead j
            for (int j = 0; j < i; ++j) {
                int s_j = sizes[j];
                if (w >= s_i + s_j) {
                    dp[i][w] = max(dp[i][w], dp[j][w - s_i] + s_j * s_i);
                }
            }
        }
    }

    int result = 0;
    for (int i = 0; i < n; ++i) {
        result = max(result, dp[i][max_weight]);
    }
    cout << result << '\n';
    return 0;
}