修复代码错误:解决添加点问题
非常抱歉给您带来困扰。我重新检查了代码,并发现了错误。在更新dp[i][j]时,我应该使用dp[pre][j-1]而不是dp[pre][j]。同时,我需要在外层循环中添加一个额外的循环来处理自由添加的点。
这是经过修正的代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> points;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
points.push_back({x, y});
}
sort(points.begin(), points.end());
int ans = 0;
vector<vector<int>> dp(n + k + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= n + k; i++) {
for (int j = 1; j <= n; j++) {
for (int pre = 0; pre < i; pre++) {
if (points[pre].second <= points[i - 1].second) {
dp[i][j] = max(dp[i][j], dp[pre][j - 1] + 1);
}
}
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
ans = max(ans, dp[i][j]);
}
}
cout << ans << endl;
return 0;
}
这段修正后的代码应该能够正确解决这个问题。非常抱歉给您带来的困扰,希望这次的代码可以正常工作。
原文地址: http://www.cveoy.top/t/topic/bs9a 著作权归作者所有。请勿转载和采集!