洛谷 P5414 分析（别看）
2026-07-09 15:19:25
发布于：河北
9阅读
0回复
0点赞
1 题目
1.1 题目所需求出内容
对于本题，最终要求：一个最小值
1.2 题目背景、允许、禁止与限制
背景：有一个由 个数字组成的序列
允许：每次操作可以将一个数字移动到任何一个位置，移动的代价为这个数字本身
禁止：
限制：求最终使得整个序列成为单调不减所需的最小代价
1.3 题目数据范围与猜测
1.4 一句话概括题意
有一个数字序列。每次操作可以将一个数字移动到任何一个位置，移动的代价为这个数字本身。求最终使得整个序列成为单调不减所需的最小代价
2 题目破题推导
注：以下七种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维，逆向思维转正向思维
正向思维：求最小代价
逆向思维：要想让代价最小，就需要让不动部分尽可能大。然后这题又要求“单调不减”。所以这道题就变成了一个算式：
2.3 分情况考虑
2.4 数学
2.5 以终为始、以始为终
2.6 手动推导
2.7 边界测试
3 模型匹配
格式为："关键词：...... "
关键词：最大不下降子序列
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;
}
有帮助，赞一个