交付独立设计 DP 状态

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

这是这条路线的最终作品。前四步的代码已经合在一起，补全状压版 tsp 和暴力版 tsp_brute，然后一次验完五条：0/1 背包 20、完全背包 25；二维和一维答案相同、格子数从 44 降到 11；石子合并 19、最长回文子序列 4；网格路径 10、放一块石头之后 4、编辑距离 3；四城 TSP 状压和暴力都是 18。五条全过输出 验收通过，否则输出 验收失败。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 第四步三个二维 DP DP 表太大内存超限先想什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
using Item = pair<int, int>;   // (重量, 价值)

const vector<Item> ITEMS = {{3, 8}, {4, 9}, {5, 11}};

vector<vector<long long>> knap2d(const vector<Item>& items, int cap) {
    int n = items.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(cap + 1, 0));
    for (int i = 1; i <= n; i++) {
        auto [w, v] = items[i - 1];
        for (int c = 0; c <= cap; c++) {
            dp[i][c] = dp[i - 1][c];
            if (c >= w && dp[i - 1][c - w] + v > dp[i][c]) dp[i][c] = dp[i - 1][c - w] + v;
        }
    }
    return dp;
}

vector<long long> knap1d(const vector<Item>& items, int cap) {
    vector<long long> dp(cap + 1, 0);
    for (auto [w, v] : items) {
        for (int c = cap; c >= w; c--) {
            if (dp[c - w] + v > dp[c]) dp[c] = dp[c - w] + v;
        }
    }
    return dp;
}

vector<long long> knap_full(const vector<Item>& items, int cap) {
    vector<long long> dp(cap + 1, 0);
    for (auto [w, v] : items) {
        for (int c = w; c <= cap; c++) {
            if (dp[c - w] + v > dp[c]) dp[c] = dp[c - w] + v;
        }
    }
    return dp;
}

long long merge_cost(const vector<int>& a) {
    int n = a.size();
    const long long INF = 1000000000000000000LL;
    vector<long long> pre(n + 1, 0);
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
    vector<vector<long long>> dp(n, vector<long long>(n, 0));
    for (int L = 2; L <= n; L++) {
        for (int i = 0; i + L - 1 < n; i++) {
            int j = i + L - 1;
            dp[i][j] = INF;
            for (int k = i; k < j; k++) {
                long long t = dp[i][k] + dp[k + 1][j] + pre[j + 1] - pre[i];
                if (t < dp[i][j]) dp[i][j] = t;
            }
        }
    }
    return dp[0][n - 1];
}

int lps(const string& s) {
    int n = s.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));
    for (int i = n - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for (int j = i + 1; j < n; j++) {
            if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}
const vector<vector<int>> GRID = {{0, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 0, 0}};

long long paths(int m, int n) {
    vector<vector<long long>> dp(m, vector<long long>(n, 1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
    return dp[m - 1][n - 1];
}

long long paths_ob(const vector<vector<int>>& g) {
    int m = g.size(), n = g[0].size();
    vector<vector<long long>> dp(m, vector<long long>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] == 1) continue;
            if (i == 0 && j == 0) {
                dp[i][j] = 1;
                continue;
            }
            long long up = i > 0 ? dp[i - 1][j] : 0;
            long long left = j > 0 ? dp[i][j - 1] : 0;
            dp[i][j] = up + left;
        }
    }
    return dp[m - 1][n - 1];
}

int edit(const string& a, const string& b) {
    int m = a.size(), n = b.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
        }
    }
    return dp[m][n];
}

const vector<vector<int>> D4 = {{0, 5, 9, 4}, {5, 0, 3, 8}, {9, 3, 0, 6}, {4, 8, 6, 0}};

int tsp(const vector<vector<int>>& d) {
    int n = d.size();
    const int INF = 1000000000;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;
    // TODO: 枚举状态 s 和当前城市 u（u 必须在 s 里、dp[s][u] 不是 INF）
    // TODO: 再枚举还没去过的 v，用 dp[s][u] + d[u][v] 更新 dp[s | (1 << v)][v]
    int full = (1 << n) - 1, best = INF;
    for (int u = 1; u < n; u++) best = min(best, dp[full][u] + d[u][0]);
    return best;
}

int tsp_brute(const vector<vector<int>>& d) {
    int n = d.size();
    vector<int> order;
    for (int i = 1; i < n; i++) order.push_back(i);
    int best = 1000000000;
    // TODO: 用 next_permutation 枚举 1..n-1 的每种顺序：从 0 出发按顺序走一圈再回 0，取最短
    return best;
}

int main() {
    auto d2 = knap2d(ITEMS, 10);
    auto d1 = knap1d(ITEMS, 10);
    vector<bool> checks;
    checks.push_back(d1[10] == 20 && knap_full(ITEMS, 10)[10] == 25);
    checks.push_back(d2[3][10] == d1[10] && d2.size() * d2[0].size() == 44 && d1.size() == 11);
    checks.push_back(merge_cost({4, 1, 2, 3}) == 19 && lps("bbbab") == 4);
    checks.push_back(paths(3, 4) == 10 && paths_ob(GRID) == 4 && edit("horse", "ros") == 3);
    checks.push_back(tsp(D4) == 18 && tsp_brute(D4) == 18);
    bool ok = true;
    for (bool c : checks) ok = ok && c;
    cout << (ok ? "验收通过" : "验收失败") << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

交付独立设计 DP 状态

更多题目

全部评论