算法
(dp) $O(n)$
一道比较有意思的dp题
记 dp[i][j]
: 在收集完所有颜色 $i$ 的球之后位于这种颜色的球的最左侧($j = 0$),或最右侧($j = 1$)
假设红球的ID小于蓝球的ID:
状态转移:
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::max;
using std::vector;
using P = std::pair<int, int>;
using ll = long long;
int main() {
int n;
cin >> n;
const int INF = 1001001001;
vector<int> l(n, INF), r(n, -INF);
rep(i, n) {
int x, c;
cin >> x >> c;
--c;
l[c] = min(l[c], x);
r[c] = max(r[c], x);
}
vector<P> d;
d.emplace_back(0, 0);
rep(i, n) if (l[i] != INF) d.emplace_back(l[i], r[i]);
d.emplace_back(0, 0);
vector<ll> dp(2);
const ll LINF = 1ll << 60;
for (int i = 1; i < d.size(); ++i) {
vector<ll> p(2, LINF);
swap(p, dp);
int l = d[i].first, r = d[i].second;
rep(j, 2) {
int x = j ? d[i - 1].second : d[i - 1].first;
dp[0] = min(dp[0], p[j] + std::abs(x - r) + (r - l));
dp[1] = min(dp[1], p[j] + std::abs(x - r) + (r - l));
}
}
cout << dp[0] << '\n';
return 0;
}
dp[1] = min(dp[1], p[j] + std::abs(x - r) + (r - l));
佬是故意这样写的吗
?
应该是abs(x-l) (写的很好,我学会了)蟹蟹