AtCoder Beginner Contest 263 (D) DP

1. D - Left Right Operation DP

https://atcoder.jp/contests/abc263/tasks/abc263_d

1.1 Problem Statement

给定一个序列 $a_1, a_2, …, a_n$, 长度为 $n$

有如下操作:

• 选定数字 $x(0 \le x \le n)$, 如果 $x = 0$, 什么也不做, 否则将序列 $a_1, a_2, …, a_x$中的每个数都替换为 $L$
• 选定数字 $y(0 \le y \le n)$, 如果 $y = 0$, 什么也不做, 否则将序列 $n_{n - y + 1}, …,a_{n - 1}, a_n$中的每个数都替换为 $R$

每种操作只能执行 一次

问: 操作之后, 整个序列 $a_1, a_2, …, a_n$ 的 和sum 的最小值 ???

1.2 分析

1.2.1 方法1

• 定义 $pre[i]$ : 表示前 $i$ 个数执行或者不执行 操作一 之后所能达到的 最小值

• 定义 $suf[i]$ : 表示后 $n - i$ 个数执行或者不执行 操作二 之后所能达到的 最小值

最后, 枚举每个分界点(前半部分操作1, 后半部分操作2), 得到全局的最小值即为最终答案

1.2.2 方法2

选择数字 $x$ 和 $y$ 并执行对应操作之后, 序列变为 $l, l, l, a_i, a_{i + 1}, a_j, r, r, r$

• 定义 $dp[0][i]$ : 表示前 $i$ 个元素执行操作一, 所能达到的最小值
• 定义 $dp[1][i]$ : 表示前 $i$ 个元素什么操作也不做, 所能达到的最小值
• 定义 $dp[2][i]$ : 表示前 $i$ 个元素执行操作二, 所能达到的最小值

转移时:

• $dp[0][i] = dp[0][i - 1] + l$
• $dp[1][i] = min(dp[0][i], dp[1][i - 1] + a[i])$
• $dp[2][i] = min(dp[2][i - 1] + r, dp[1][i])$

1.3 code

#include <bits/stdc++.h>

using namespace std;

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

    long long n, l, r;
    cin >> n >> l >> r;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    long long ans = 1e18;

    vector<long long> pre(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        pre[i] = min(pre[i - 1] + a[i], l * i);
    }

    vector<long long> suf(n + 2, 0);
    for (int i = n; i >= 1; i--)
    {
        suf[i] = min(suf[i + 1] + a[i], r * (n + 1 - i));
    }

    for (int i = 1; i <= n; i++)
    {
        // left
        ans = min(ans, pre[i] + suf[i + 1]);
        // right
        ans = min(ans, pre[i - 1] + suf[i]);
    }

    cout << ans << endl;

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

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

    long long n, l, r;
    cin >> n >> l >> r;

    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }

    vector<vector<long long>> dp(3, vector<long long>(n + 1, 1e18));
    dp[0][0] = dp[1][0] = dp[2][0] = 0;

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

    cout << dp[2][n] << endl;

    return 0;
}