波波牛的惩罚
我们先处理出每个数可能影响的数，可以用链式前向星或 vector
我们维护一个队列，在最开始的时候放入最小值。
每次取出一个数，然后遍历所有可以影响的数，并把影响成功的数放进队列。
在最后判一下是否相同即可。
复杂度 \(O(n)\)。
点击展开代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
#define eb emplace_back
constexpr int N = 1e6 + 10;
int a[N], c[N], len, n, ans[N];
vector<int>d[N];
bool vis[N];
bool solve(){int mi = 1e9;FL(i, 1, n)mi = min(mi, a[i]);queue<int>q;FL(i, 1, n)if(a[i] == mi)q.emplace(i), vis[i] = 1;while(!q.empty()){int w = q.front();q.pop();for(int z : d[w]){if(vis[z])continue;vis[z] = 1, q.emplace(z);if(a[z] != mi)a[z] = mi, ans[++len] = z;}}FL(i, 1, n)if(a[i] != mi)return 0;return 1;
}
int32_t main(){cin.tie(0)->sync_with_stdio(0);cin >> n;FL(i, 1, n)cin >> a[i];FL(i, 1, n)cin >> c[i];FL(i, 1, n)d[c[i]].emplace_back(i);if(!solve())cout << -1 << endl;else{cout << len << endl;FL(i, 1, len)cout << ans[i] << " ";}return 0;
}
波波牛的飞船
Easy
我们有个显然的 DP：
\(dp_i = \min_{1 \le j < i} dp_j + dis(i, j) \times (dis(i, j) + q_j)\)
直接 \(O(n ^ 2)\) 暴力维护即可。
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
#define eb emplace_back
constexpr int N = 1e6 + 10;
#define int long long
int n, x[N], dp[N], p[N];
int32_t main(){cin.tie(0)->sync_with_stdio(0);cin >> n;FL(i, 1, n)cin >> x[i];FL(i, 1, n)cin >> p[i];memset(dp, 0x5f, sizeof dp);dp[1] = 0;FL(i, 2, n)FL(j, 1, i - 1)dp[i] = min(dp[i], dp[j] + (x[i] - x[j]) * ((x[i] - x[j]) + p[j]));cout << dp[n] << endl;return 0;
}
Hard
找最小的 \(j\) 还是太慢了，我们把式子继续拆分：
\[\begin{aligned}
dp_i &= \min_{1 \le j < i} dp_j +(x_i - x_j)^2 + p_j(x_i - x_j) \\
&= \min_{1 \le j < i} dp_j +x_i^2 +x_j^2 - 2x_ix_j +x_ip_j - x_jp_j \\
&= x_i^2 + \min_{1 \le j < i} dp_j + x_j^2 - 2x_ix_j +x_ip_j - x_jp_j. \\
\end{aligned}
\]
定义：
\[\begin{aligned}
f_j(x) &= dp_j + x_j^2 - 2xx_j +xp_j - x_jp_j \\
&= (p_j - 2x_j)x +(dp_j +x_j^2 - x_jp_j).
\end{aligned}
\]
那么最后 \(dp_i = x_i^2 + \min_{1 \le j < i}f_j(x_i)\)，其中 \(dp_1 = 0\)。
\(f_j()\) 用李超线段树即可，最后复杂度 \(O(n \log n)\)。
点击展开代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a, b, c) for(int a = (b), a##end = (c); a <= a##end; a++)
#define FR(a, b, c) for(int a = (b), a##end = (c); a >= a##end; a--)
#define lowbit(x) ((x) & -(x))
#define eb emplace_back
constexpr int N = 1e6 + 10;
#define int long long
int n, p[N], x[N], dp[N];
#define index(l, r) ((l) + (r) | (l) != (r))
#define u index(l, r)
#define ls index(l, mid)
#define rs index(mid + 1, r)
#define mid ((l) + (r) >> 1)
struct line{int a, b;int calc(int x){return a * x + b;}
}L[N];
int w[N << 1];
int query(int l, int r, int x){if(!w[u] || x < l || r < x)return 1e18;int ans = L[w[u]].calc(x);if(l == r)return ans;return min({ans, query(l, mid, x), query(mid + 1, r, x)});
}
void modify(int l, int r, int k){if(!w[u])return void(w[u] = k);if(L[k].calc(mid) - L[w[u]].calc(mid) < 0)swap(k, w[u]);if(L[k].calc(l) - L[w[u]].calc(l) < 0)modify(l, mid, k);if(L[k].calc(r) - L[w[u]].calc(r) < 0)modify(mid + 1, r, k);
}
int32_t main(){cin.tie(0)->sync_with_stdio(0);cin >> n;FL(i, 1, n)cin >> x[i];FL(i, 1, n)cin >> p[i];L[1].a = p[1] - 2 * x[1], L[1].b = x[1] * (x[1] - p[1]);modify(1, 1e6, 1);FL(i, 2, n){dp[i] = x[i] * x[i] + query(1, 1e6, x[i]);L[i].a = p[i] - 2 * x[i], L[i].b = dp[i] + x[i] * (x[i] - p[i]);modify(1, 1e6, i);}cout << dp[n] << endl;return 0;
}