求调:得了65分,用的递归,显示7个WA;
#include<bits/stdc++.h>
using namespace std;
struct num {
int ind, thi;
} a[200002];
bool cmp(num a, num b) {
if (a.thi != b.thi) return a.thi < b.thi;
return a.ind < b.ind;
}
int main() {
int T, n, x = 0, A[200002] = {0}, ans = 0, tot = 0, C[200002] = {0}, D[200002] = {0}, E[200002] = {0};
cin >> T;
for (int j = 1; j <= T; j++) {
tot = 0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i]; // 正向读入数组
for (int i = 1; i <= n; i++) { // 从左到右处理
if (i == n || A[i] != A[i + 1]) { // 比较下一个元素
tot++;
D[tot] = A[i];
a[tot].ind = tot;
a[tot].thi = A[i];
} else {
ans += A[i];
}
}
sort(a + 1, a + 1 + tot, cmp);
for (int i = 1; i <= tot; i++) {
if (i == 1 || a[i].thi != a[i - 1].thi)
E[a[i].ind] = -1;
else
E[a[i].ind] = a[i - 1].ind;
}
C[1] = 0;
for (int i = 2; i <= tot; i++) {
if (E[i] == -1)
x = 0;
else
x = C[E[i] + 1] + D[i];
C[i] = max(x, C[i - 1]);
}
ans += C[tot];
cout << ans << endl;
ans = 0;
memset(C, 0, sizeof(C)); // 重置避免污染后续测试用例
}
return 0;
}