动态规划题目详解
|
miyan
|
174
|
动态规划

4173 字
|
42 分钟

1.Vacations

链接：https://codeforces.com/problemset/problem/698/A

思路：

    定义 \(dp[i][j]\) 为第 \(i\) 天为 \(j\) 时前 \(i\) 天最小休息天数。

  • \(j == 0\): 休息
  • \(j == 1\): 比赛
  • \(j == 2\): 健身

    初始化 \(dp[0][0] = dp[0][1] = dp[0][2] = 0\) 表示前 \(0\) 天休息 \(0\) 天。

    状态转移：

  • 由于可以无限休息，那么第 \(i\) 天休息时最少天数为：
    • \(dp[i][0] = min({dp[i – 1][0], dp[i – 1][1], dp[i – 1][2]}) + 1\)
  • 如果第 \(i\) 天想要参加比赛那么需要 \(a[i] == 1\) 或者 \(a[i] == 3\)，此时 \(dp[i][1]\) 为：
    • \(dp[i][1] = min(dp[i – 1][0], dp[i – 1][2])\)
  • 如果第 \(i\) 天想要健身那么需要 \(a[i] == 2\) 或者 \(a[i] == 3\)，此时 \(dp[i][1]\) 为：
    • \(dp[i][2] = min(dp[i – 1][0], dp[i – 1][1])\)

代码：

const int inf = 1e9;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (auto &x : a | views::drop(1))
        cin >> x;

    vector<array<int, 3>> dp(n + 1, {inf, inf, inf});

    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for (int i = 1; i <= n; ++i)
    {
        dp[i][0] = min({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}) + 1;

        if (a[i] == 1 || a[i] == 3)
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]);
        if (a[i] == 2 || a[i] == 3)
            dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]);
    }

    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << endl;
}

2.Basketball Exercise

链接：https://codeforces.com/contest/1195/problem/C

思路：

    定义 \(dp[i][j]\) 为第 \(i\) 列状态为 \(j\) 时 \(i \text{ ~ } n\) 的最大身高总和。

  • \(j == 0\): 不选择第 \(i\) 列的任何人。
  • \(j == 1\): 选择第一行的第 \(i\) 位同学。
  • \(j == 2\): 选择第二行的第 \(i\) 位同学。

    状态转移：

  • 如果第 \(i\) 列不选择任何人，显然可以通过 \(i + 1\) 列的任何状态转移而来，既：
    • \(dp[i][0] = max({dp[i + 1][0], dp[i + 1][1], dp[i + 1][2]});\)
  • 如果第 \(i\) 列选择第一行的人，那么可以通过第 \(i + 1\) 列的 \(j = 2\) 和第 \(i + 2\) 列的 \(j = 2\)状态转移而来，既：
    • \(dp[i][1] = max(dp[i + 1][2], dp[i + 2][2]) + h1[i];\)
  • 如果第 \(i\) 列选择第二行的人，那么可以通过第 \(i + 1\) 列的 \(j = 1\) 和第 \(i + 2\) 列的 \(j = 1\)状态转移而来，既：
    • \(dp[i][2] = max(dp[i + 1][1], dp[i + 2][1]) + h2[i];\)

    最后的答案就为第一行的三个状态中的最大值。

代码：

void solve()
{
    int n;
    cin >> n;
    vector<ll> h1(n), h2(n);
    for (auto &x : h1)
        cin >> x;
    for (auto &x : h2)
        cin >> x;

    vector<array<ll, 3>> dp(n + 2, {0, 0, 0});
    for (int i = n - 1; ~i; --i)
    {
        dp[i][0] = max({dp[i + 1][0], dp[i + 1][1], dp[i + 1][2]});

        dp[i][1] = max(dp[i + 1][2], dp[i + 2][2]) + h1[i];

        dp[i][2] = max(dp[i + 1][1], dp[i + 2][1]) + h2[i];
    }

    cout << max({dp[0][0], dp[0][1], dp[0][2]});
}

3.Woodcutters

链接：https://codeforces.com/contest/545/problem/C

思路：

    定义 \(dp[i][j]\) 为第 \(i\) 颗树状态为 \(j\) 时前 \(i\) 颗树最多砍倒的树木数量。

  • \(j == 0\): 不砍第 \(i\) 颗树。
  • \(j == 1\): 砍第 \(i\) 颗树并且向左倒。
  • \(j == 2\): 砍第 \(i\) 颗树并且向右倒。

    状态转移：

  • 如果不砍第 \(i\) 颗树，显然可以通过前 \(i – 1\) 颗的任何状态转移而来，既：
    • \(dp[i][0] = max({dp[i – 1][0], dp[i – 1][1], dp[i – 1][2]});\)
  • 如果砍第 \(i\) 颗树并且向左倒，那么可以通过：
    • 不砍第 \(i – 1\) 颗树或者砍第 \(i – 1\) 颗树并且向左倒转移而来，此时只需判断一下当前树的高度在向左倒时会不会碰到第 \(i – 1\) 颗树的基底，既：
      • \(if (a[i][0] – a[i][1] > a[i – 1][0]) \)
      • \(    dp[i][1] = max({dp[i][0], dp[i – 1][1] + 1, dp[i – 1][0] + 1});\)
    • 砍第 \(i – 1\) 颗树并且向右倒转移而来，此时需要判断上一颗树的基底 + 高度是不是小于当前树的基底 – 高度，既：
      • \(if (a[i][0] – a[i][1] > a[i – 1][0] + a[i – 1][1])\)
      • \(    dp[i][1] = max(dp[i][0], dp[i – 1][2] + 1);\)
  • 如果砍第 \(i\) 颗树并且向右倒，那么只需判断一下当前树的基底 + 高度是不是小于下一颗树的基底，如果满足那么就可以通过前一颗树的任意情况转移而来，既：
    • \(if (a[i][0] + a[i][1] < a[i + 1][0])\)
    • \(    dp[i][2] = max({dp[i – 1][0], dp[i – 1][1], dp[i – 1][2]}) + 1;\)

    最后的答案就为第一行的三个状态中的最大值。

代码：

void solve()
{
    int n;
    cin >> n;
    vector<array<int, 2>> a(n + 1);
    for (auto &[x, y] : a | views::drop(1))
        cin >> x >> y;

    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }

    vector<array<int, 3>> dp(n + 1, {0, 0, 0});
    for (int i = 2; i <= n - 1; ++i)
    {
        dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});

        if (a[i][0] - a[i][1] > a[i - 1][0])
            dp[i][1] = max({dp[i][0], dp[i - 1][1] + 1, dp[i - 1][0] + 1});
        if (a[i][0] - a[i][1] > a[i - 1][0] + a[i - 1][1])
            dp[i][1] = max(dp[i][0], dp[i - 1][2] + 1);

        if (a[i][0] + a[i][1] < a[i + 1][0])
            dp[i][2] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]}) + 1;
    }

    cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) + 2 << endl;
}

4.k-Tree

链接：https://codeforces.com/contest/431/problem/C

思路：

    定义 \(dp[i][j]\) 为树的前缀边权和为 \(i\) 是否路过边权大于等于 d 的边为 \(j\) 的方案数。

  • \(j == 0\): 没有路过。
  • \(j == 1\): 路过。

    记忆化搜索：

  • 从 \(dp[0][0]\) 开始搜索。
  • 每次搜索都查 \(dp\) 表，如果当前 \(dp[i][j]\) 不为 \(-1\)，直接复用。
  • 如果为 \(-1\) 就从当前状态展开，循环遍历 \(1\) ~ \(k\) 的所有值，大于等于 \(d\) 就标记，然后递归找更小的子结构。
  • 每次搜索都存储当前状态的值。

代码：

void solve()
{
    ll n, k, d;
    cin >> n >> k >> d;

    vector<array<ll, 2>> dp(n + 1, {-1, -1});
    auto dfs = [&](auto &&self, ll sum, bool ok) -> ll
    {
        if (sum == n)
            return ok;

        ll &cur = dp[sum][ok];

        if (cur != -1)
            return cur;

        cur = 0;
        for (int i = 1; i <= k; ++i)
        {
            if (sum + i > n)
                break;

            bool now = (i >= d);

            cur = (cur + self(self, sum + i, ok | now)) % MOD;
        }

        return cur;
    };

    cout << dfs(dfs, 0, 0) % MOD << endl;
}

5.Flowers

链接：https://codeforces.com/contest/474/problem/D

思路：

    爬楼梯变种。

    定义 \(dp[i]\) 为选择 \(i\) 朵花的方案数。

    初始化 \(dp[0] = 1\) 表示选择 \(0\) 朵花有 \(1\) 种方案数。

    状态转移：

  • 如果当前选择红花那么就由 \(dp[i – 1]\) 直接转移而来。
  • 如果当前选择白花，需判断 \(i\) 是否大于等于 \(k\) ，如果满足就可由 \(dp[i – k]\) 转移而来。

    后续前缀和处理一下即可，不过多赘述。

代码：

void solve()
{
    int t, k;
    cin >> t >> k;

    int n = 1e5;
    vector<ll> dp(n + 1, 0);
    vector<ll> s(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = (dp[i] + dp[i - 1]) % MOD;

        if (i >= k)
            dp[i] = (dp[i] + dp[i - k]) % MOD;

        s[i] = (s[i - 1] + dp[i]) % MOD;
    }

    while (t--)
    {
        int a, b;
        cin >> a >> b;

        cout << (s[b] - s[a - 1] + MOD) % MOD << endl;
    }
}

6.Consecutive Subsequence

链接：https://codeforces.com/contest/977/problem/F

思路：

    最长上升子序列变种。

    由于只需找到最长连续上升子序列，所以只需在哈希表中动态存储当前遍历到的元素的前面所有元素的最大出现位置即可。

    定义 \(dp[i]\) 为 以 \(a[i]\) 结尾的最长连续上升子序列的长度。

    状态转移：

    对于每个 \(a[i]\)，只需判断哈希表中是否存在 \(a[i] – 1\) 即可，如果存在那么转移方程就为：

\(    dp[i] = max(dp[i], dp[m[a[i] – 1]] + 1);\)

    通过遍历得到最大值后，逆序找到所有元素即可，详细见代码实现。

代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    map<int, int> m;
    vector<int> dp(n, 1);
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        if (m.count(a[i] - 1))
            dp[i] = max(dp[i], dp[m[a[i] - 1]] + 1);

        m[a[i]] = i;

        ans = max(ans, 1ll * dp[i]);
    }

    cout << ans << endl;

    int val = -1;
    for (int i = 0; i < n; ++i)
    {
        if (dp[i] == ans)
        {
            val = a[i];
            break;
        }
    }

    val -= ans - 1;
    for (int i = 0; i < n; ++i)
    {
        if (a[i] == val)
        {
            cout << i + 1 << ' ';
            ++val;
        }
    }

    cout << endl;
}

7.Caesar’s Legions

链接：https://codeforces.com/contest/118/problem/D

思路：

    定义 \(dp[i][j][0/1]\) 为步兵排列了 \(i\) 人，骑兵排列了 \(j\)，最后放置的是 步兵/骑兵 的方案数。

    初始化 \(dp[0][0][0] = dp[0][0][1] = 1\) 表示两种兵都排列 \(0\) 人，方案数为 \(1\) 种。

    由于 \(n1\) 和 \(n2\) 都非常小，直接双重循环枚举放置 \(i\) 个步兵，\(j\) 个骑兵，对于每次遍历通过以前的状态更新当前位置是 \(1\) ~ \(min(n, k, i / j)\) 个步兵或骑兵结尾的状态：

  • 如果当前位置以步兵结尾，状态转移为：
    • \(for (int k = 1; k <= min({n1, k1, i}); ++k)\)
      \(dp[i][j][0] = (dp[i][j][0] + dp[i – k][j][1]) \text{% MOD};\)
  • 如果当前位置以骑兵结尾，状态转移为：
    • \(for (int k = 1; k <= min({n2, k2, j}); ++k)\)
      \( dp[i][j][1] = (dp[i][j][1] + dp[i][j – k][0]) \text{% MOD};\)

    最终答案就为两种状态的和，既：\((dp[n1][n2][1] + dp[n1][n2][0]) \text{% MOD}\)。

代码：

void solve()
{
    int n1, n2, k1, k2;
    cin >> n1 >> n2 >> k1 >> k2;

    vector dp(n1 + 1, vector<array<ll, 2>>(n2 + 1, {0, 0}));
    dp[0][0][0] = dp[0][0][1] = 1;
    for (int i = 0; i <= n1; ++i)
    {
        for (int j = 0; j <= n2; ++j)
        {
            if (i + j)
            {
                for (int k = 1; k <= min({n1, k1, i}); ++k)
                    dp[i][j][0] = (dp[i][j][0] + dp[i - k][j][1]) % MOD;

                for (int k = 1; k <= min({n2, k2, j}); ++k)
                    dp[i][j][1] = (dp[i][j][1] + dp[i][j - k][0]) % MOD;
            }
        }
    }

    cout << (dp[n1][n2][1] + dp[n1][n2][0]) % MOD << endl;
}

8.Sending a Sequence Over the Network

链接：https://codeforces.com/contest/1741/problem/E

思路：

    定义 \(dp[i]\) 为 \(a[i]\) 当做某个段的前缀或后缀的可行度（\(0/1\)）。

    状态转移：

  • 如果想要让当前 \(a[i]\) 当作段的后缀那么必须保证前面最少有 \(a[i]\) 个元素，如果满足那么转移方程就为：
    • \(dp[i] |= dp[i – a[i] – 1];\)
  • 如果想要让当前 \(a[i]\) 当作段的前缀那么必须保证后面最少有 \(a[i]\) 个元素，如果满足那么转移方程就为：
    • \(dp[i + a[i]] |= dp[i – 1];\)

    最后答案就为 \(dp[n]\) , 如果为真就代表满足，否则不满足。

代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (auto &x : a | views::drop(1))
        cin >> x;

    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (i + a[i] <= n)
            dp[i + a[i]] |= dp[i - 1];
        if (i - a[i] - 1 >= 0)
            dp[i] |= dp[i - a[i] - 1];
    }

    if (dp[n])
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

9.George and Job

链接：https://codeforces.com/contest/467/problem/C

思路：

    定义 \(dp[i][j]\) 为在前 \(i\) 个整数内选择了 \(j\) 段序列的最大和。

    状态转移：

  • 显然的对于每个 \(dp[i][j]\) 都可以通过 \(dp[i – 1][j]\) 转移而来。
  • 对于当前 \(i\) 它可以作为某段的开头需要满足它后面有足够的位置，既它本身和后面有至少 \(m\) 个元素，此时就可以尝试在当前位置放置第 \(j\) 个序列，第 \(j\) 个序列需要满足前面有足够的位置，既当前 \(i\) 需满足前面有至少 \(i / m\) 个序列，满足以上条件后，状态转移方程就为：
    • \(dp[i + m – 1][j] = max(dp[i + m – 1][j], dp[i – 1][j – 1] + s[i + m – 1] – s[i – 1]);\)

代码：

void miyan()
{
    ll n, m, k;
    cin >> n >> m >> k;
    vector<ll> p(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> p[i];

    vector<ll> s(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        s[i] = s[i - 1] + p[i];

    vector dp(n + 1, vector<ll>(k + 1, 0));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= k; ++j)
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);

        if (i + m - 1 <= n)
        {
            for (int j = 1; j <= k && j <= i / m + 1; ++j)
                dp[i + m - 1][j] = max(dp[i + m - 1][j], dp[i - 1][j - 1] + s[i + m - 1] - s[i - 1]);
        }
    }

    cout << dp[n][k] << endl;
}

10.Make Them Equal

链接：https://codeforces.com/contest/1633/problem/D

思路：

    \(01\) 背包问题。

    求出每个数字所需的最少操作次数，跑一遍 \(01\) 背包即可。

    对于求得每个数字的最小操作次数，由于数字的范围为 \(1000\)，直接暴力双重循环枚举前 \(1000\) 个数字的最小操作次数即可。

    \(01\) 背包详见：背包问题 – MiyanLog

代码：

vector<ll> d(1010, INT_MAX);
void init()
{
    d[1] = 0;
    for (int i = 1; i <= 1000; ++i)
    {
        for (int x = 1; x <= i; ++x)
        {
            ll j = i + i / x;

            if (j <= 1000)
                d[j] = min(d[j], d[i] + 1);
        }
    }
}

void miyan()
{
    ll n, k;
    cin >> n >> k;
    vector<ll> b(n), c(n);
    for (auto &x : b)
        cin >> x;
    for (auto &x : c)
        cin >> x;

    ll s = 0;
    for (auto x : b)
        s += d[x];

    if (s <= k)
    {
        cout << accumulate(all(c), 0ll) << endl;
        return;
    }

    vector<ll> dp(k + 1, 0);
    for (int i = 0; i < n; ++i)
    {
        for (int j = k; j >= d[b[i]]; --j)
        {
            dp[j] = max(dp[j], dp[j - d[b[i]]] + c[i]);
        }
    }

    cout << dp[k] << endl;
}

11.Non-Descending Arrays

链接：https://codeforces.com/contest/2144/problem/C

思路：

    定义 \(dp[i][0/1]\) 为第 \(i\) 个元素交换与否前缀升序的方案数。

    那么对于每个 \(i\) 就只有交换和不交换两种情况。

    状态转移：

  • 当 \(a[i] >= a[i – 1]\) 并且 \(b[i] >= b[i – 1]\) 时对于 \(i\) 就可以通过以下状态转移而来：
    • 不交换 \(i – 1\) 并且不交换 \(i\)，既 \(dp[i][0] = (dp[i][0] + dp[i – 1][0]) \text{% MOD} \)
    • 交换 \(i – 1\) 并且 交换 \(i\)，既 \(dp[i][1] = (dp[i][1] + dp[i – 1][1]) \text{% MOD} \)
  • 当 \(a[i] >= b[i – 1]\) 并且 \(b[i] >= a[i – 1]\) 时对于 \(i\) 就可以通过以下状态转移而来：
    • 不交换 \(i – 1\) 并且交换 \(i\)，既 \(dp[i][1] = (dp[i][1] + dp[i – 1][0]) \text{% MOD} \)
    • 交换 \(i – 1\) 并且 不交换 \(i\)，既 \(dp[i][0] = (dp[i][0] + dp[i – 1][1]) \text{% MOD} \)

代码：

void miyan()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;

    vector dp(n, array<ll, 2>());
    dp[0][0] = dp[0][1] = 1;
    for (int i = 1; i < n; ++i)
    {
        if (a[i] >= a[i - 1] && b[i] >= b[i - 1])
        {
            dp[i][0] = (dp[i][0] + dp[i - 1][0]) % MOD;
            dp[i][1] = (dp[i][1] + dp[i - 1][1]) % MOD;
        }

        if (a[i] >= b[i - 1] && b[i] >= a[i - 1])
        {
            dp[i][0] = (dp[i][0] + dp[i - 1][1]) % MOD;
            dp[i][1] = (dp[i][1] + dp[i - 1][0]) % MOD;
        }
    }

    cout << (dp[n - 1][0] + dp[n - 1][1]) % MOD << endl;
}

12.Road Optimization

链接：https://codeforces.com/contest/1625/problem/C

思路：

    定义 \(dp[i][j]\) 为到达第 \(i\) 个位置，恰好删了 \(j\) 个标志牌的最小时间，当前牌子可能删除

    初始化 \(dp[1][i] = 0\)

    状态转移：

        为了转移到 \(i\)，需要选择上一个保留下来的位置 \(p（1 <= p <= i – 1）\)，把 \([p, i]\) 之间的全部牌都删除，于是这一步一共删了 \(t = (i – 1) – p\) 个。

        所有从 \(d[p]\) 到 \(d[i]\) 之间的全部路都要按 \(a[p]\) 的速度跑，时间为 \((d[i] – d[p]) * a[p]\)。

        对于如何选择上一个位置，枚举 \(i\) 到 \(p\) 之间删了几个牌 \(t\) 即可，上一个牌的下标就为 \(p = i – 1 – t\)。

代码：

void miyan()
{
    int n, L, k;
    cin >> n >> L >> k;
    vector<ll> d(n + 2), a(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> d[i];
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    d[n + 1] = L;

    vector dp(n + 2, vector<ll>(k + 1, INT_MAX));

    fill(all(dp[1]), 0);

    for (int i = 2; i <= n + 1; ++i)
        for (int j = 0; j <= k && j <= i - 1; ++j)
            for (int t = 0; t <= j; ++t)
                dp[i][j] = min(dp[i][j], dp[i - t - 1][j - t] + (d[i] - d[i - t - 1]) * a[i - t - 1]);

    cout << ranges::min(dp[n + 1]) << endl;
}

13.Mysterious Present

链接：https://codeforces.com/contest/4/problem/D

思路：

    最长上升子序列变种，\(n\) 为 \(5000\)，二重循环版即可。

    先将所有放不下贺卡的信封筛掉，然后对 {长，宽} 二元组进行排序，跑一遍最长上升子序列，对于输出方案，对每一个元素都记录上一个元素是谁，逆序找到所有元素，再逆序输出即可。

代码：

void miyan()
{
    ll n, w, h;
    cin >> n >> w >> h;
    vector<array<int, 3>> a;
    a.reserve(n);
    for (int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        if (x > w && y > h)
            a.push_back({x, y, i + 1});
    }

    n = a.size();

    if (!n)
    {
        cout << 0 << endl;
        return;
    }

    ranges::sort(a);

    vector<int> dp(n, 1);
    vector<int> pre(n, -1);
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            if (a[i][0] > a[j][0] && a[i][1] > a[j][1])
            {
                if (dp[j] >= dp[i])
                {
                    dp[i] = dp[j] + 1;
                    pre[i] = j;
                }
            }
        }
    }

    ll ans = ranges::max(dp);
    cout << ans << endl;

    for (int i = 0; i < n; ++i)
    {
        if (dp[i] == ans)
        {
            vector<int> pos;
            pos.reserve(n);
            pos.push_back(a[i][2]);

            int now = i;
            while (pre[now] != -1)
            {
                now = pre[now];
                pos.push_back(a[now][2]);
            }

            for (auto x : pos | views::reverse)
                cout << x << ' ';
            cout << endl;

            break;
        }
    }
}

14.Make The Fence Great Again

链接：https://codeforces.com/contest/1221/problem/D

思路：

    定义 \(dp[i][j]\) 为第 \(i\) 块木板增加 \(j\) 次的最小代价。

    可以发现对于当前元素 \(i\)，想让它与相邻元素不同，其最多 \(+2\)，既 \(+0\)，\(+1\)，\(+2\) 就可以保证全部相邻元素全部不同。

    直接枚举 \(i – 1\) 加 \(0\) \(1\) \(2\) 的情况，\(i\) 加 \(0\) \(1\) \(2\) 的情况，在两个元素不相等的情况下转移即可。

代码：

void miyan()
{
    const ll inf = 1e18 + 10;

    int n;
    cin >> n;
    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> a[i] >> b[i];

    vector<array<ll, 3>> dp(n + 1, {inf, inf, inf});
    fill(all(dp[0]), 0ll);
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= 2; ++j)
            for (int k = 0; k <= 2; ++k)
                if (a[i] + j != a[i - 1] + k)
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + j * b[i]);

    cout << ranges::min(dp[n]) << endl;
}

15.Forbidden Difference

链接：https://atcoder.jp/contests/abc403/tasks/abc403_d

思路：

    先将所有元素都存入到桶中，然后将桶中的所有元素进行分组，分组规则如下：

  • \(x\) 为序列中先前为分组的元素，将其以及 \(x + k/cotsd\) 加入到数组中。

    此时这个数组中的元素需要删掉一些，既使得剩下的元素不相邻，使用 \(dp\) 解。

    定义 \(dp[i]\) 为删除数组中第 \(i\) 个元素，前 \(i\) 个元素需要删掉的最小元素个数。

    初始化定义 \(dp[0] = 0\)。

    状态转移：

  • 对于 \(dp[i]\) 其可以通过删除上上个元素或者上一个元素转移而来，状态转移方程为：
    • \(dp[i] = min({dp[i], dp[i – 1] + m[v[i – 1]], dp[i – 2] + m[v[i – 1]]})\)

    \(m[v[i]]\) 为原始序列中值为 \(v[i]\) 的元素个数。

代码：

void miyan()
{
    int n, d;
    cin >> n >> d;
    vector<int> a(n);
    for (int i = 0; i < n; ++i)
        cin >> a[i];

    map<int, int> m;
    for (auto x : a)
        ++m[x];

    if (d == 0)
    {
        cout << n - m.size() << endl;
        return;
    }

    ll maxx = ranges::max(a);
    ll ans = 0;
    vector<int> st(maxx + 10, 0);
    vector<int> v;
    v.reserve(n);
    for (auto [x, y] : m)
    {
        if (!st[x])
        {
            for (int i = x; i < maxx + 5; i += d)
            {
                if (!st[i] && m.count(i))
                {
                    st[i] = 1;
                    v.push_back(i);
                }
                else
                    break;
            }

            vector<ll> dp(v.size() + 1, INT_MAX);
            dp[0] = 0;
            for (int i = 1; i <= v.size(); ++i)
            {
                if (i == 1)
                    dp[i] = min(dp[i], dp[i - 1] + m[v[i - 1]]);
                else
                    dp[i] = min({dp[i], dp[i - 1] + m[v[i - 1]], dp[i - 2] + m[v[i - 1]]});
            }

            ans += min(dp[v.size()], dp[v.size() - 1]);

            v.clear();
        }
    }

    cout << ans << endl;
}
动态规划
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
背包问题

							
							

							
动态规划题目推荐

							
							

							
数字三角形模型

							
							

							
最大子数组和