洛谷 P5414 分析（别看）

科技起源的小号1

2026-10-15 19:54:14

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：有一个由 $n$ 个数字组成的序列
允许：每次操作可以将一个数字移动到任何一个位置，移动的代价为这个数字本身
限制：求最终使得整个序列成为单调不减所需的最小代价

1.3 题目数据范围与猜测

$1 \le t \le 10 ,1 \le n \le 10^2 \longrightarrow O(tn^2)$

1.4 一句话概括题意

有一个数字序列。每次操作可以将一个数字移动到任何一个位置，移动的代价为这个数字本身。求最终使得整个序列成为单调不减所需的最小代价

2 题目破题推导

2.1 第一步：正向思维转逆向思维，逆向思维转正向思维

正向思维：求最小代价
逆向思维：要想让代价最小，就需要让不动部分尽可能大。然后这题又要求“单调不减”。所以这道题就变成了一个算式： $总和-最大不下降子序列$

3 模型匹配

关键词：最大不下降子序列 $\longrightarrow$ $\huge{动态规划}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int t;
int n;
const int N = 1e2 + 10;
int a[N], dp[N];

int main(){

    cin >> t;
    while(t--){
        cin >> n;
        int sum = 0;
        for (int i = 1;i <= n;i++){
            cin >> a[i];
            dp[i] = a[i];
            sum += a[i];
        }
        for (int i = 2;i <= n;i++){
            for (int j = 1;j < i;j++){
                if (a[j] <= a[i]){
                    dp[i] = max(dp[i], dp[j] + a[i]);
                }
            }
        }
        int mx = INT_MIN;
        for (int i = 1;i <= n;i++){
            mx = max(mx, dp[i]);
        }
        cout << sum - mx << endl;
    }
    
    return 0;
}