解决思路
- 还是先从二维数组开始，定义一个二维数组\(dp\)，对于 \(dp[i,j]\)，\(i\) 表示第 \(i\) 个元素，\(j\) 表示当前元素的状态(正数或负数)
\(dp[i,0]\) 表示第 \(i\) 个元素为负数时，前 \(i\) 个元素中需要改动的元素数；
\(dp[i,1]\) 表示第 \(i\) 个元素为正数时，前 \(i\) 个元素中需要改动的元素数
#include <bits/stdc++.h>
int main() {
std::freopen("input.txt", "r", stdin);
std::freopen("output.txt", "w", stdout);
int n;
std::cin >> n;
std::vector<int> t(n + 1, 0);
for (int i = 1; i <= n; ++i) std::cin >> t[i];
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(2, 0));
if (t[1] == 0) ++dp[1][0], dp[1][1] = n+1;
else if (t[1] < 0) dp[1][1] = n+1;
else dp[1][0] = 1, dp[1][1] = n+1;
for (int i = 2; i <= n; ++i) {
if (t[i] < 0) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = std::min(dp[i - 1][0], dp[i - 1][1]) + 1;
} else if (t[i] == 0) {
dp[i][0] = dp[i - 1][0] + 1;
dp[i][1] = std::min(dp[i - 1][0], dp[i - 1][1]) + 1;
} else {
dp[i][0] = dp[i - 1][0] + 1;
dp[i][1] = std::min(dp[i - 1][0], dp[i - 1][1]);
}
}
std::cout << dp[n][1] << std::endl;
return 0;
}
误区
按照题目要求，正数和负数都必须有非零个。因此，需要实现时需要满足两个条件
- 第一个元素必须是负数
- 对于 \(dp[1][1]\)，将其设置为 \(n+1\)，表示不可达（在后续代码中可以发现，任何涉及到 \(dp[i-1][1]\) 的都在 \(min\) 函数中）
- 最后一个元素必须是正数
- 输出 \(dp[n][1]\) 即可
更好的解
同样地，在二维数组的基础上，优化一下判断以及将其转换成一维数组
#include <bits/stdc++.h>
int main() {
std::freopen("input.txt", "r", stdin);
std::freopen("output.txt", "w", stdout);
int n;
std::cin >> n;
std::vector<int> t(n + 1, 0);
for (int i = 1; i <= n; ++i) std::cin >> t[i];
std::vector<int> dp(2, 0);
if (t[1] >= 0) dp[0] = 1;
dp[1] = n + 1;
for (int i = 2; i <= n; ++i) {
// dp[1] 必须先于 dp[0] 更新，因为 dp[1] 依赖于未更新的 dp[0]
dp[1] = std::min(dp[0], dp[1]);
if (t[i] <= 0) dp[1] += 1;
if (t[i] >= 0) ++dp[0];
}
std::cout << dp[1] << std::endl;
return 0;
}