You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
51 lines
2.1 KiB
51 lines
2.1 KiB
/*
|
|
问题描述：
|
|
小美有一个长度为 n 的数组 a1,a2,.·,an ，他可以对数组进行如下操作:
|
|
1.删除第一个元素 a1，同时数组的长度减一，花费为x
|
|
2.删除整个数组，花费为k*MEX(a)，其中MEX(a)表示a中未出现过的最小非负整数。例如[0,1,2,4]的 MEX为3。
|
|
小美想知道将 a 数组全部清空的最小代价是多少。
|
|
输入描述：
|
|
每个测试文件均包含多组测试数据。第一行输入一个整数T代表数据组数，每组测试数据描述如下第二行输入三个正整数：n,k,x
|
|
代表数组中的元素数量、删除整个数组的花费系数、删除单个元素的花费。第三行输入n个整数 a1, a2,...,an表示数组元素。
|
|
除此之外，保证所有的a之和不超过 2x105.
|
|
*/
|
|
|
|
/*
|
|
思路：动态规划+维护最小未出现的整数
|
|
dp[i]表示从i往后考虑的最小花费，最后的最小花费就是dp[0]和直接删除后续所有元素的最小值
|
|
对于删除后续所有的元素的选项，我们必须要知道mex是多少，可以在更新dp的过程中，用一个变量不断的更新当前的最小未出现的整数
|
|
虽然这里出现了两次循环的嵌套，但是并不会重置参数，因此复杂度是O(n)
|
|
*/
|
|
#include <iostream>
|
|
#include <vector>
|
|
#include <algorithm>
|
|
#include <set>
|
|
using namespace std;
|
|
|
|
int main() {
|
|
int T;
|
|
cin >> T; // 读取测试数据组数
|
|
while (T--) {
|
|
long long n, k, x;
|
|
cin >> n >> k >> x;
|
|
vector<long long> a(n);
|
|
for (int i = 0; i < n; ++i) {
|
|
cin >> a[i];
|
|
}
|
|
// 动态规划数组dp[i]表示从i往后考虑的最小花费，最后最小花费就是dp[0]或者直接删除后续所有元素
|
|
vector<long long> dp(n + 1, LLONG_MAX);
|
|
dp[n] = 0;
|
|
int suffix_mex = 0;
|
|
set<int> vst;
|
|
for (int i = n-1; i >= 0; --i) {
|
|
vst.insert(a[i]);
|
|
while(vst.count(suffix_mex)){
|
|
suffix_mex++;
|
|
}
|
|
dp[i] = min(dp[i + 1] + x, k * suffix_mex);
|
|
}
|
|
// 输出最小花费
|
|
cout << dp[0] << endl;
|
|
}
|
|
return 0;
|
|
}
|