A，B，C，D水
E题建边时贪心，只要建x值最近，y值最近，z值最近三条边就行了
#include <bits/stdc++.h>
using namespace std;
long long n, fa[100005], top, aa, bb, ans, cnt;
struct sd {
long long x, y, z, k;
} a[100005], ls[100005];
struct sb {
long long u, v, w;
} b[1000005];
int find(int x) {
if (fa[x] == x)
return x;
else
return fa[x] = find(fa[x]);
}
int cmp1(sd A, sd B) { return A.x < B.x; }
int cmp2(sd A, sd B) { return A.y < B.y; }
int cmp3(sd A, sd B) { return A.z < B.z; }
int cmp4(sb A, sb B) { return A.w < B.w; }
void add(int j) {
top++;
b[top].u = a[j - 1].k;
b[top].v = a[j].k;
b[top].w = min(abs(a[j].x - a[j - 1].x), min(abs(a[j].y - a[j - 1].y), abs(a[j].z - a[j - 1].z)));
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].z);
a[i].k = i;
}
for (int i = 1; i <= n; i++) fa[i] = i;
sort(a + 1, a + n + 1, cmp1);
for (int i = 2; i <= n; i++) {
add(i);
}
for (int i = 1; i <= n; i++) ls[i] = a[i];
sort(a + 1, a + n + 1, cmp2);
for (int i = 2; i <= n; i++) {
add(i);
}
sort(a + 1, a + n + 1, cmp3);
for (int i = 2; i <= n; i++) {
add(i);
}
sort(b + 1, b + top + 1, cmp4);
for (int i = 1; i <= top; i++) {
aa = find(b[i].u);
bb = find(b[i].v);
if (aa != bb) {
fa[aa] = bb;
cnt++;
ans += b[i].w;
if (cnt == n - 1)
break;
}
}
cout << ans;
return 0;
}
F题把序列翻转，就变成LICS问题了
#include <bits/stdc++.h>
using namespace std;
int f[5005][5005], a[5005], b[5005], n, Max, ans;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) b[i] = a[n - i + 1];
for (int i = 1; i <= n; i++) {
Max = 0;
for (int j = 1; j <= n - i + 1; j++) {
f[i][j] = f[i - 1][j];
if (a[i] > b[j] && Max < f[i - 1][j])
Max = f[i - 1][j];
if (a[i] == b[j]) {
if (j == n - i + 1)
f[i][j] = Max + 1;
else
f[i][j] = Max + 2;
}
ans = max(ans, f[i][j]);
}
}
cout << ans;
return 0;
}