25.6 แบบฝึกหัด

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, capacity;
    cin >> n >> capacity;
    vector<long long> best(capacity + 1, 0);
    for (int i = 0; i < n; i++) {
        int weight;
        long long value;
        cin >> weight >> value;
        for (int c = capacity; c >= weight; c--) {
            best[c] = max(best[c], best[c - weight] + value);
        }
    }
    cout << best[capacity] << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, length;
    cin >> n >> length;
    vector<long long> best(length + 1, 0);
    for (int i = 0; i < n; i++) {
        int piece;
        long long price;
        cin >> piece >> price;
        for (int c = piece; c <= length; c++) {
            best[c] = max(best[c], best[c - piece] + price);
        }
    }
    cout << best[length] << '\n';
    return 0;
}

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

const long long MOD = 1000000007;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows, cols;
    cin >> rows >> cols;
    vector<long long> ways(cols, 0);
    ways[0] = 1;
    for (int r = 0; r < rows; r++) {
        string line;
        cin >> line;
        for (int c = 0; c < cols; c++) {
            if (line[c] == '#') {
                ways[c] = 0;
            } else if (c > 0) {
                ways[c] = (ways[c] + ways[c - 1]) % MOD;
            }
        }
    }
    cout << ways[cols - 1] << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> above(m + 1, 0), row(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                row[j] = above[j - 1] + 1;
            } else {
                row[j] = max(above[j], row[j - 1]);
            }
        }
        swap(above, row);
    }
    cout << above[m] << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> tails;
    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        auto it = lower_bound(tails.begin(), tails.end(), value);
        if (it == tails.end()) {
            tails.push_back(value);
        } else {
            *it = value;
        }
    }
    cout << tails.size() << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    vector<int> above(m + 1), row(m + 1);
    for (int j = 0; j <= m; j++) {
        above[j] = j;
    }
    for (int i = 1; i <= n; i++) {
        row[0] = i;
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                row[j] = above[j - 1];
            } else {
                row[j] = 1 + min({above[j - 1], above[j], row[j - 1]});
            }
        }
        swap(above, row);
    }
    cout << above[m] << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows, cols;
    cin >> rows >> cols;
    vector<vector<long long>> to_end(rows, vector<long long>(cols));
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            cin >> to_end[r][c];
        }
    }
    for (int r = rows - 1; r >= 0; r--) {
        for (int c = cols - 1; c >= 0; c--) {
            if (r == rows - 1 && c == cols - 1) {
                continue;
            }
            if (r == rows - 1) {
                to_end[r][c] += to_end[r][c + 1];
            } else if (c == cols - 1) {
                to_end[r][c] += to_end[r + 1][c];
            } else {
                to_end[r][c] += max(to_end[r + 1][c], to_end[r][c + 1]);
            }
        }
    }
    string path;
    int r = 0, c = 0;
    while (r < rows - 1 || c < cols - 1) {
        if (c == cols - 1 || (r < rows - 1 && to_end[r + 1][c] >= to_end[r][c + 1])) {
            path += 'D';
            r++;
        } else {
            path += 'R';
            c++;
        }
    }
    cout << to_end[0][0] << '\n' << path << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> boxes(n);
    for (int i = 0; i < n; i++) {
        cin >> boxes[i].first >> boxes[i].second;
    }
    sort(boxes.begin(), boxes.end(), [](const pair<int, int> &a, const pair<int, int> &b) {
        if (a.first != b.first) {
            return a.first < b.first;
        }
        return a.second > b.second;
    });
    vector<int> tails;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(tails.begin(), tails.end(), boxes[i].second);
        if (it == tails.end()) {
            tails.push_back(boxes[i].second);
        } else {
            *it = boxes[i].second;
        }
    }
    cout << tails.size() << '\n';
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long length;
        cin >> length;
        prefix[i] = prefix[i - 1] + length;
    }
    vector<vector<long long>> cost(n + 2, vector<long long>(n + 2, 0));
    for (int span = 2; span <= n; span++) {
        for (int i = 1; i + span - 1 <= n; i++) {
            int j = i + span - 1;
            long long best = LLONG_MAX;
            for (int k = i; k < j; k++) {
                best = min(best, cost[i][k] + cost[k + 1][j]);
            }
            cost[i][j] = best + prefix[j] - prefix[i - 1];
        }
    }
    cout << cost[1][n] << '\n';
    return 0;
}

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

const int INF = 1000000000;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<vector<int>> dist(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    int urgent = 0;
    for (int i = 0; i < k; i++) {
        int shop;
        cin >> shop;
        urgent |= 1 << shop;
    }
    if (n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    int full = (1 << n) - 1;
    vector<vector<int>> best(1 << n, vector<int>(n, INF));
    best[1][0] = 0;
    for (int mask = 1; mask <= full; mask++) {
        bool urgent_done = (mask & urgent) == urgent;
        for (int last = 0; last < n; last++) {
            if (best[mask][last] == INF) {
                continue;
            }
            for (int next = 0; next < n; next++) {
                if ((mask & (1 << next)) != 0) {
                    continue;
                }
                if ((urgent & (1 << next)) == 0 && !urgent_done) {
                    continue;
                }
                int grown = mask | (1 << next);
                best[grown][next] = min(best[grown][next], best[mask][last] + dist[last][next]);
            }
        }
    }
    int answer = INF;
    for (int last = 1; last < n; last++) {
        answer = min(answer, best[full][last] + dist[last][0]);
    }
    cout << answer << '\n';
    return 0;
}