A29400. 园林修整
题目描述
园林修整
题目描述
园林修整中，常利用树木来形成整齐的区域分割线。园丁要将树木按高度修剪成递增或递减的形状 —— 如果一棵树太高了，就需要裁剪；如果太矮了，则需要替换。修整所花费的力气与裁剪或替换树木的数量成正比，所以需要你替他想一种最省力的修整方案。
时间限制：10000 内存限制：65536
输入
输入第一行给出一个正个整数 N (3 ≤ N ≤ 2000)，随后一行给出 N 个正整数的树高。所有整数在区间 [1, 103] 内，同行数字间以空格分隔。
输出
首先在一行中输出需要被裁剪或替换的树木的最少数量。第二行从左到右列出这些树木的编号（从 1 开始）。如果解不唯一，输出那个需要最少替换树木的解，题目保证这样的解是唯一的。 同行数字间必须以 1 个空格分隔，行首尾不得有多余空格。 如果没有树需要调整，则根据树高的升降性质，在一行中输出 Non-ascending（表示“非递增”）或 Non-descending（表示非递减）。
样例输入
样例1：
10
2 3 8 2 4 5 10 1 7 11样例2：
3
1 2 3样例输出
样例1：
4
2 3 7 8样例2：
Non-descending提示
样例1解释： 首先，要将树木修整成按高度非递减的样式，我们需要调整 4 棵树；而要修整成非递增样式，则需要调整 7 棵树。所以我们应选择递增序列对应的解。 其次，存在 4 种不同的递增序列解：
1、保持树高为 2、3、4、5、10、11 的树不变，我们需要替换掉高度为 2、1、7 的 3 棵树，因为它们太矮了；
2、保持树高为 2、3、4、5、7、11 的树不变，我们需要替换掉高度为 2、1 的 2 棵树；
3、保持树高为 2、2、4、5、10、11 的树不变，我们需要替换掉高度为 1、7 的 2 棵树；
4、保持树高为 2、2、4、5、7、11 的树不变，我们只需要替换掉高度为 1 的 1 棵树。 所以最后选择输出第(4)组解，即裁剪编号为 2、3、7（对应高度为 3、8、10）的树，替换掉第 8 棵高度为 1 的树。
参考答案
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
struct Result {
int changes;
int replaces;
vector<int> removed;
};
Result processDirection(const vector<int>& a, bool nonDecreasing) {
int n = a.size();
vector<int> dp(n, 1);
vector<int> prev(n, -1);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
bool valid = nonDecreasing ? (a[j] <= a[i]) : (a[j] >= a[i]);
if (valid && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
}
int maxLen = *max_element(dp.begin(), dp.end());
vector<int> candidates;
for (int i = 0; i < n; ++i) {
if (dp[i] == maxLen) {
candidates.push_back(i);
}
}
int bestReplace = 1e9;
vector<int> bestIndices;
for (int candidate : candidates) {
vector<int> path;
int current = candidate;
while (current != -1) {
path.push_back(current);
current = prev[current];
}
reverse(path.begin(), path.end());
set<int> pathSet(path.begin(), path.end());
vector<int> sortedPath(path.begin(), path.end());
sort(sortedPath.begin(), sortedPath.end());
int replace = 0;
for (int k = 0; k < n; ++k) {
if (pathSet.count(k)) continue;
auto it = upper_bound(sortedPath.begin(), sortedPath.end(), k);
if (it != sortedPath.begin()) {
int leftIdx = *(--it);
if (a[k] < a[leftIdx]) {
replace++;
}
}
}
if (replace < bestReplace || (replace == bestReplace && path.size() > bestIndices.size())) {
bestReplace = replace;
bestIndices = sortedPath;
}
}
set<int> reserved(bestIndices.begin(), bestIndices.end());
vector<int> removed;
for (int i = 0; i < n; ++i) {
if (!reserved.count(i)) {
removed.push_back(i + 1);
}
}
sort(removed.begin(), removed.end());
return { n - maxLen, bestReplace, removed };
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> a(N);
for (int i = 0; i < N; ++i) {
cin >> a[i];
}
bool isNonDescending = true;
for (int i = 1; i < N; ++i) {
if (a[i] < a[i-1]) {
isNonDescending = false;
break;
}
}
if (isNonDescending) {
cout << "Non-descending\n";
return 0;
}
bool isNonAscending = true;
for (int i = 1; i < N; ++i) {
if (a[i] > a[i-1]) {
isNonAscending = false;
break;
}
}
if (isNonAscending) {
cout << "Non-ascending\n";
return 0;
}
Result asc = processDirection(a, true);
Result desc = processDirection(a, false);
bool useAsc;
if (asc.changes < desc.changes) {
useAsc = true;
} else if (asc.changes > desc.changes) {
useAsc = false;
} else {
useAsc = (asc.replaces <= desc.replaces);
}
Result res = useAsc ? asc : desc;
cout << res.changes << '\n';
for (size_t i = 0; i < res.removed.size(); ++i) {
if (i > 0) cout << ' ';
cout << res.removed[i];
}
cout << '\n';
return 0;
}