这道题是一道有一定思维难度的 DP 题目。
首先讲 \(\Theta(n^2)\) 做法：预处理每一个行星最远能够直接到达的那个行星，记作 \(nxt_i\)。接着上转移方程。设 \(f_i\) 为到达第 \(i\) 个行星需要执行的最小加注次数。初始 \(f_1=0,f_2=f_3=\cdots=f_n=\infty\) 容易列出转移方程：
\(f_j=\min(f_j,f_i+1)\quad({i+1\leq j \leq nxt_i})\)
根据题意，第一问的答案为 \(ans=f_n\)。但如果 \(f_n=inf\)，则说明无解，要输出数字 \(0\)。
马上写出代码：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
const int inf = 1e9 + 7;
int n;
int a[N];
int pre[N], nxt[N];
int f[N];
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {nxt[pre[a[i]]] = i;pre[a[i]] = i;}f[0] = 0;for (int i = 2; i <= n; i++) {f[i] = inf;}int last = 0;for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= nxt[i]; j++) {if (f[i] + 1 < f[j]) {f[j] = f[i] + 1;}}}if (f[n] == inf) {cout << 0 << endl;return 0;}cout << f[n] << endl;return 0;
}
但这里第二问怎么办呢？我们在 DP 的时候记录 \(frm_i\)，表示可以到达第 \(i\) 个行星的距离最近那个行星。然后记录一个变量 \(now=n\) 和一个栈 \(ans\)。让 \(now=frm[now]\)，随后将 \(now\) 压入 \(ans\)，一直进行这个操作直到 \(frm[now]=0\)。最后只需要输出 \(ans\) 里的值就可以了。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
const int inf = 1e9 + 7;
int n;
int a[N];
int pre[N], nxt[N];
int frm[N];
int f[N];
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {nxt[pre[a[i]]] = i;pre[a[i]] = i;}f[0] = 0;for (int i = 2; i <= n; i++) {f[i] = inf;}int last = 0;for (int i = 1; i <= n; i++) {for (int j = max(last, i + 1); j <= nxt[i]; j++) {if (f[i] + 1 < f[j]) {f[j] = f[i] + 1;frm[j] = i;last = j;}}}if (f[n] == inf) {cout << 0 << endl;return 0;}cout << f[n] << endl;stack<int> ans;int now = n;while (frm[now]) {now = frm[now];ans.push(now);}while (!ans.empty()) {cout << ans.top() << " ";ans.pop();}cout << endl;return 0;
}
且慢！这么做只能获得 50pts。为什么？因为 \(n\leq30000\)，而我们的时间复杂度是 \(\Theta(n^2)\)。
考虑优化：我们容易发现 \(f\) 单调不降（应该是可以使用斜率优化的，但比较慢），于是记录一个 \(last\) 为当前已经计算过的行星的编号最大值。这样我们每次遍历 \(j\) 的时候起点变成了 \(\max(i+1,last)\)（保持正确性的原因是如果前面计算过它，后面再次计算一定是不优的）。
代码如下：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
const int inf = 1e9 + 7;
int n;
int a[N];
int pre[N], nxt[N];
int frm[N];
int f[N];
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];}for (int i = 1; i <= n; i++) {nxt[pre[a[i]]] = i;pre[a[i]] = i;}f[0] = 0;for (int i = 2; i <= n; i++) {f[i] = inf;}int last = 0;for (int i = 1; i <= n; i++) {for (int j = max(last, i + 1); j <= nxt[i]; j++) {if (f[i] + 1 < f[j]) {f[j] = f[i] + 1;frm[j] = i;last = j;}}}if (f[n] == inf) {cout << 0 << endl;return 0;}cout << f[n] << endl;stack<int> ans;int now = n;while (frm[now]) {now = frm[now];ans.push(now);}while (!ans.empty()) {cout << ans.top() << " ";ans.pop();}cout << endl;return 0;
}
结果你发现：这个代码时间复杂度是 \(\Theta(n)\) 的，AC 了。