P1877 [HAOI2012] 音量调节

yanbinmu · 2024-12-26 19:31:42 · 题解

分析

观察数据大小不难发现一个性质：

对于每一个阶段而言，可能的音量大小的个数不会超出 maxLeval = 5000。

而这启发我们用 set 维护计算到某一位得到的所有可能音量大小。

对于复杂度，我们每一次做的操作数最多为 set 大小，而操作数不超过 50，显然绰绰有余。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 55;

int c[N]; 

set<int> x, y;

int main() {
    int n, maxn, b;
    cin >> n >> b >> maxn;
    for(int i = 1;i <= n;i ++ ) {
        cin >> c[i];
    }
    x.insert(b);
    for(int i = 1;i <= n;i ++ ) {
        if(i % 2 == 1) {
            for(int j : x) {
                if(j - c[i] >= 0) y.insert(j - c[i]);
                if(j + c[i] <= maxn) y.insert(j + c[i]);
            }
            x.clear();
        }
        else {
            for(int j : y) {
                if(j - c[i] >= 0) x.insert(j - c[i]);
                if(j + c[i] <= maxn) x.insert(j + c[i]);
            }
            y.clear();
        }
    }
    int ans = -1;
    if(n % 2 == 1) {
        for(int j : y) ans = max(ans, j);
    }
    else for(int j : x) ans = max(ans, j);
    cout << ans;
    return 0;
}