原题链接
1 题目
1.1 题目所需求出内容
对于本题,最终要求:一个最小值
1.2 题目背景、允许、禁止与限制
背景:有一个由 nnn 个数字组成的序列
允许:每次操作可以将一个数字移动到任何一个位置,移动的代价为这个数字本身
禁止:
限制:求最终使得整个序列成为单调不减所需的最小代价
1.3 题目数据范围与猜测
1≤t≤10,1≤n≤102⟶O(tn2)1 \le t \le 10 ,1 \le n \le 10^2 \longrightarrow O(tn^2)1≤t≤10,1≤n≤102⟶O(tn2)
1.4 一句话概括题意
有一个数字序列。每次操作可以将一个数字移动到任何一个位置,移动的代价为这个数字本身。求最终使得整个序列成为单调不减所需的最小代价
2 题目破题推导
> 注:以下七种方法都可以考虑一下
2.1 大拆小、小组大
2.2 正向思维转逆向思维,逆向思维转正向思维
正向思维:求最小代价
逆向思维:要想让代价最小,就需要让不动部分尽可能大。然后这题又要求“单调不减”。所以这道题就变成了一个算式:总和−最大不下降子序列总和-最大不下降子序列总和−最大不下降子序列
2.3 分情况考虑
2.4 数学
2.5 以终为始、以始为终
2.6 手动推导
2.7 边界测试
3 模型匹配
> 格式为:"关键词:...... ⟶\longrightarrow⟶ ......\huge{......}......"
关键词:最大不下降子序列 ⟶\longrightarrow⟶ 动态规划\huge{动态规划}动态规划
4 最终代码(禁止抄袭,仅用于参考)