题目链接

小红的好数组

题目描述

小红定义一个数组为“好数组”，当且仅当这个数组至少存在一个长度为 3 的非降序子数组（连续的）。

小红可以进行多次操作，每次操作可以修改数组中的一个元素的值为任意整数。

小红想知道，至少需要操作几次，才可以把这个数组变成“不是好数组”。

解题思路

这个问题的目标是消除所有长度为 3 的非降序子数组。这是一个典型的动态规划问题，因为当前位置的决策依赖于之前的状态，并且我们需要求解一个最优值（最少操作次数）。

1. “不是好数组”的结构

一个数组“不是好数组”，意味着对于任意索引 ，都不满足 。

换句话说，一个“不是好数组”中，最长的连续非降序子数组的长度不能超过 2。

2. 动态规划设计

我们可以定义一个 DP 状态来记录到当前位置为止，形成一个合法的（“不是好数组”）前缀所需的最小代价。关键信息是，这个前缀的非降序后缀有多长，因为它会影响下一个元素的决策。

  • DP 状态定义:

    dp[i][1]: 使前缀 合法，且其结尾的非降序子数组长度为 1 (即 )，所需的最小修改次数。

    dp[i][2]: 使前缀 合法，且其结尾的非降序子数组长度为 2 (即 )，所需的最小修改次数。

  • DP 状态转移:

    在计算 时，我们从 的状态转移而来。对于 ，我们有两种选择：保留它，或者修改它。

    • 计算 dp[i][1] (结尾长度为 1):

      • 修改 : 我们可以把 修改成任意小的值，确保 。此时，前一个状态 结尾是长度 1 或 2 都可以。我们取代价更小的那个。 代价 =

      • 保留 : 仅当 时，保留 才能形成长度为 1 的后缀。 代价 =

      • 取上述两种可行选择的最小值。

    • 计算 dp[i][2] (结尾长度为 2):

      • 要形成长度为 2 的后缀， 的后缀长度必须为 1（否则会形成长度为 3 的）。

      • 修改 : 我们可以把 修改成任意大的值，确保 。 代价 =

      • 保留 : 仅当 时，保留 才能形成长度为 2 的后缀。 代价 =

      • 取上述两种可行选择的最小值。

  • 初始条件与答案:

    • 初始: (保留第一个元素，后缀长度为1)， (无法形成长度为2的后缀)。

    • 答案: 。

代码

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

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

    vector<vector<int>> dp(n, vector<int>(3, INF));

    dp[0][1] = 0; // 保留a[0]，后缀长度1，代价0

    for (int i = 1; i < n; ++i) {
        // 计算 dp[i][1]
        int prev_best = min(dp[i - 1][1], dp[i - 1][2]);
        // 选项1: 修改 a[i]
        dp[i][1] = min(dp[i][1], prev_best + 1);
        // 选项2: 保留 a[i]
        if (a[i - 1] > a[i]) {
            dp[i][1] = min(dp[i][1], prev_best);
        }

        // 计算 dp[i][2]
        int prev_len1_best = dp[i - 1][1];
        // 选项1: 修改 a[i]
        dp[i][2] = min(dp[i][2], prev_len1_best + 1);
        // 选项2: 保留 a[i]
        if (a[i - 1] <= a[i]) {
            dp[i][2] = min(dp[i][2], prev_len1_best);
        }
    }

    cout << min(dp[n - 1][1], dp[n - 1][2]) << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        if (n <= 2) {
            System.out.println(0);
            return;
        }

        final int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[n][3];
        for (int[] row : dp) {
            Arrays.fill(row, INF);
        }
        
        dp[0][1] = 0;

        for (int i = 1; i < n; i++) {
            // 计算 dp[i][1]
            int prevBest = Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = Math.min(dp[i][1], prevBest + 1);
            if (a[i - 1] > a[i]) {
                dp[i][1] = Math.min(dp[i][1], prevBest);
            }

            // 计算 dp[i][2]
            int prevLen1Best = dp[i - 1][1];
            dp[i][2] = Math.min(dp[i][2], prevLen1Best + 1);
            if (a[i - 1] <= a[i]) {
                dp[i][2] = Math.min(dp[i][2], prevLen1Best);
            }
        }

        System.out.println(Math.min(dp[n - 1][1], dp[n - 1][2]));
    }
}

import sys

def solve():
    n_str = sys.stdin.readline()
    if not n_str: return
    n = int(n_str)
    
    a = list(map(int, sys.stdin.readline().split()))

    if n <= 2:
        print(0)
        return

    INF = float('inf')
    dp = [[INF, INF] for _ in range(n)] # dp[i][0] for len 1, dp[i][1] for len 2
    
    dp[0][0] = 0

    for i in range(1, n):
        # 计算 dp[i][0] (len 1)
        prev_best = min(dp[i-1][0], dp[i-1][1])
        # 选项1: 修改 a[i]
        dp[i][0] = min(dp[i][0], prev_best + 1)
        # 选项2: 保留 a[i]
        if a[i-1] > a[i]:
            dp[i][0] = min(dp[i][0], prev_best)
            
        # 计算 dp[i][1] (len 2)
        prev_len1_best = dp[i-1][0]
        # 选项1: 修改 a[i]
        dp[i][1] = min(dp[i][1], prev_len1_best + 1)
        # 选项2: 保留 a[i]
        if a[i-1] <= a[i]:
            dp[i][1] = min(dp[i][1], prev_len1_best)

    print(min(dp[n-1][0], dp[n-1][1]))

solve()

算法及复杂度

  • 算法：动态规划

  • 时间复杂度: ，因为我们只需要对数组进行一次线性遍历来填充 DP 表。

  • 空间复杂度: ，用于存储 DP 表。可以优化到 ，因为 只依赖于 。