机试第12章

最大连续子序列和

const int MAXN = 10000;
long long a[MAXN], dp[MAXN];

long long solve(int n)
{
    long long res = 0;
    dp[0] = a[0];
    for (int i = 1; i < n; ++i)
    {
        dp[i] = max(a[i], dp[i - 1] + a[i]);
        res = max(res, dp[i]);
    }
    return res;
}

最长递增子序列

const int MAXN = 1000;
int a[MAXN], dp[MAXN];

int solve(int n)
{
    int res = 0;
    for (int i = 0; i < n; ++i)
    {
        dp[i] = 1;
        for (int j = 0; j < i; ++j)
            if (a[i] > a[j])
                dp[i] = max(dp[i], dp[j] + 1);
        res = max(res, dp[i]);
    }
    return res;
}

最大上升子序列和

const int MAXN = 1000;
int a[MAXN], dp[MAXN];

int solve(int n)
{
    int res = 0;
    for (int i = 0; i < n; ++i)
    {
        dp[i] = a[i];
        for (int j = 0; j < i; ++j)
            if (a[i] > a[j])
                dp[i] = max(dp[i], dp[j] + a[i]);
        res = max(res, dp[i]);
    }
    return res;
}

最长公共子序列

const int MAXN = 1000;
int dp[MAXN][MAXN];
char s1[MAXN], s2[MAXN];

int solve(int n, int m)
{
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            if (i == 0 || j == 0)
            {
                dp[i][j] = 0;
                continue;
            }
            else if (s1[i] == s2[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    return dp[n][m];
}

编辑距离

void solve(string &s1, string &s2)
{
    int n = s1.size(), m = s2.size();
    vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; ++i)
        f[i][0] = i;
    for (int i = 0; i <= m; ++i)
        f[0][i] = i;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            if (s1[i - 1] == s2[j - 1])
                f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j] + 1, f[i][j - 1] + 1));
            else
                f[i][j] = 1 + min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1]));
        }
    cout << f[n][m] << "\n";
}

背包问题

0-1背包

每种物品至多只能选择1件。dp[i][j]表示前 个物品装进容量为 的背包能获得的最大价值。dp[i][j]的转移仅与dp[i-1][j]和dp[i-1][j-w[i]]有关，可简化为dp[j]。

const int MAXN = 1000;
int n, m; // 物品个数，背包容量
int dp[MAXN];
int v[MAXN], w[MAXN]; // 价值，重量

int solve()
{
    for (int i = 0; i <= m; ++i)
        dp[i] = 0;
    for (int i = 0; i < n; ++i)
        for (int j = m; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[m];
}

完全背包

每个物品可以选择多件。 与0-1背包相比，仅更新dp数组时遍历顺序发生改变。

const int MAXN = 1000;
int n, m; // 物品个数，背包容量
int dp[MAXN];
int v[MAXN], w[MAXN]; // 价值，重量

int solve()
{
    for (int i = 0; i <= m; ++i)
        dp[i] = 0;
    for (int i = 0; i < n; ++i)
        for (int j = w[i]; j <= m; ++j)
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    return dp[m];
}

多重背包

每种物品最多选k件。 转化为0-1背包问题求解。

const int MAXN = 1000;
int dp[MAXN];
int v[MAXN], w[MAXN], k[MAXN];
int value[MAXN], weight[MAXN]; // 分解后的价值，质量

int solve(int n, int m)
{
    int num = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> v[i] >> w[i] >> k[i];
        for (int j = 1; j <= k[i]; j <<= 1)
        {
            value[num] = v[i] * j;
            weight[num] = w[i] * j;
            num++;
            k[i] -= j;
        }
        if (k[i] > 0)
        {
            value[num] = v[i] * k[i];
            weight[num] = w[i] * k[i];
            num++;
        }
    }

    for (int i = 0; i <= m; ++i)
        dp[i] = 0;
    for (int i = 0; i < num; ++i)
        for (int j = m; j >= weight[i]; --j)
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    return dp[m];
}