A. Penchick and Modern Monument time limit per test: 1 seconds memory limit per test:…
- User
A. Penchick and Modern Monument
time limit per test: 1 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output
题目描述
在繁华大都市马尼拉的摩天大楼中,菲律宾最新的 Noiph 购物中心刚刚竣工!建筑经理潘奇克下令用 根柱子建造一座最先进的纪念碑。
纪念碑支柱的高度可以用一个由 个正整数组成的数组 来表示,其中 代表 和 之间所有 的 个支柱的高度。
彭契克希望柱子的高度按不递减的顺序排列,即 代表 和 之间所有 。然而,由于混淆,纪念碑的柱子高度是按非递增**顺序排列的,即 代表 和 之间所有的 。
幸运的是,彭奇克可以修改石碑,并根据需要对石柱进行以下操作:
- 将支柱的高度修改为任意正整数。形式上,选择一个索引 和一个正整数 。然后指定 。
帮助潘奇克确定最少需要多少次运算才能使纪念碑支柱的高度不递减。
输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 ( )。测试用例说明如下。
每个测试用例的第一行都包含一个整数 ( ) - 柱子的数量。
每个测试用例的第二行包含 个整数 ( 和 )--支柱的高度。
**请注意,给定数组 是非递增数组。
请注意,在所有测试用例中, 的总和没有***限制。
输出格式
对于每个测试用例,输出一个整数,表示使支柱高度不递减所需的最小操作数。
样例 #1
样例输入 #1
3 5 5 4 3 2 1 3 2 2 1 1 1样例输出 #1
4 1 0提示
-
注
在第一个测试案例中,支柱的初始高度为 。
- 在第一次操作中,彭奇克将支柱 的高度改为 。
- 在第二次操作中,他将支柱的高度 改为 。
- 第三次操作是将支柱 的高度改为 。
- 在第四次操作中,将支柱 的高度改为 。
操作后,支柱的高度为 ,不递减。由此可以证明,彭契克不可能通过少于 次的操作使支柱的高度不递减。
在第二个测试案例中,彭契克可以将支柱 的高度修改为 ,从而使支柱的高度不递减。
在第三个测试案例中,柱子的高度已经不递减,因此不需要进行任何操作。
用c++写,并解释代码和思路,用中文。
- Assistant
要解决这个问题,我们需要将给定的非递增序列通过最少的操作次数转换为非递减序列。每次操作可以将任意一个支柱的高度修改为任意正整数。
思路:
-
最长非递减子序列(Longest Non-Decreasing Subsequence, LNDS): 我们需要找到原始序列中最长的非递减子序列长度。保持这个子序列的元素不变,其他需要修改。因此,最少的操作次数就是总柱子数减去LNDS的长度。
-
动态规划(Dynamic Programming): 使用动态规划来计算LNDS的长度。定义
dp[i]表示以第i个柱子结尾的最长非递减子序列的长度。- 初始化所有
dp[i] = 1,因为每个柱子至少可以单独成为一个子序列。 - 对于每个柱子
i,检查之前的柱子j(j < i),如果h[j] <= h[i],则可以将柱子i添加到以j结尾的子序列中,更新dp[i] = max(dp[i], dp[j] + 1)。 - 最终,LNDS的长度就是
dp数组中的最大值。
- 初始化所有
-
计算结果: 对于每个测试用例,输出
n - LNDS作为最少操作次数。
代码实现:
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; vector<int> h(n); for(auto &x: h) cin >> x; // dp[i] 表示以第i个元素结尾的最长非递减子序列长度 vector<int> dp(n,1); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ if(h[j] <= h[i]){ dp[i] = max(dp[i], dp[j]+1); } } } // 找到最长的非递减子序列 int lnds = *max_element(dp.begin(), dp.end()); // 最少操作次数为总柱子数减去最长非递减子序列长度 cout << (n - lnds) << "\n"; } }解释:
-
输入处理: 首先读取测试用例的数量
t。对于每个测试用例,读取柱子的数量n和高度数组h。 -
动态规划计算LNDS:
- 初始化一个长度为
n的dp数组,每个元素初始值为1。 - 使用两层循环,外层遍历每个柱子
i,内层遍历之前的柱子j。如果h[j] <= h[i],则可以将柱子i添加到以j结尾的子序列中。 - 更新
dp[i]为dp[j] + 1的最大值。
- 初始化一个长度为
-
结果输出: 找到
dp数组中的最大值,即为最长非递减子序列的长度。然后计算n - LNDS,即为最少需要修改的柱子数,并输出结果。
样例验证:
对于第一个测试用例:
- 输入序列:
5 4 3 2 1 - LNDS的长度为1(任意一个柱子)
- 最少操作次数为
5 - 1 = 4
对于第二个测试用例:
- 输入序列:
2 2 1 - LNDS的长度为2(例如前两个柱子)
- 最少操作次数为
3 - 2 = 1
对于第三个测试用例:
- 输入序列:
1 - 已经满足非递减,无需操作
- 最少操作次数为
1 - 1 = 0
复杂度分析:
- 时间复杂度:对于每个测试用例,动态规划的时间复杂度为O(n²)。由于n最大为50,且t最大为1000,总体复杂度在可接受范围内。
- 空间复杂度:使用了额外的O(n)空间来存储
dp数组。
-