求调
查看原帖
求调
1657431
yuiyui1234楼主2025/5/3 18:44

求调:得了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;
}
2025/5/3 18:44
加载中...