Atcoder Beginer Contest 306 D ~ E

vp中途突然拉肚子>_<

D - Poisonous Full-Course

D - Poisonous Full-Course (atcoder.jp)

题意

一个人初始是健康的，现在有n道菜摆在他面前，每道菜都有自已的美味值，但是有些菜是有毒的，有些菜是无毒的。如果他在健康状态吃了有毒的菜就会变成中毒状态，如果他在中毒状态吃了无毒的菜就会变回健康状态，如果他在中毒状态吃了有毒的菜就会死亡。

面对依次上前的n道菜，他可以选择吃或跳过。求得在避免死亡的状态下获得最大的美味值。

思路

简单的dp，设dp[i][j]为在第i道菜时处于j状态下的最大美味值，j为0是健康，j为1是中毒。可以推得状态转移方程，当菜无毒时，dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][0]) + y), dp[i][1] = dp[i-1][1]。当菜有毒时，dp[i][1] = max(dp[i-1][1], dp[i-1][0] + y), dp[i][0] = dp[i-1][0]。

还可用滚动数组优化，详见代码。

代码

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    array<ll, 2> dp;
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        if(x == 0) {
            dp[0] = max(dp[0], max(dp[1], dp[0]) + y);
        } else {
            dp[1] = max(dp[1], dp[0] + y);
        }
    }

    cout << max(dp[0], dp[1]) << "\n";

    return 0;
}

E - Best Performances

E - Best Performances (atcoder.jp)

题意

初始时有一个全为零的序列，然后进行若干次更改，每次更改把某个下标的数改成另一个数，每次更改后输出序列中前k个最大的数的和。

思路

用两个multiset维护前k个最大的元素和剩下的元素，再用一个数组记录真实下标对应的值，然后模拟即可。

代码

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k, q;
    cin >> n >> k >> q;

    multiset<int> s1, s2;
    vector<int> p(n + 1);
    for(int i = 0; i < n; i++) {
        if(i < n - k) {
            s1.insert(0);
        } else {
            s2.insert(0);
        }
    }

    if(s1.empty()) {
        s1.insert(-1); //防止段错误
    }

    ll ans = 0;
    while(q--) {
        int x, y;
        cin >> x >> y;
        
        auto it = s2.find(p[x]);
        
        if(it != s2.end()) {
            ans -= p[x];
            s2.erase(it);

            if(y >= *prev(s1.end())) {
                ans += y;
                s2.insert(y);
            } else {
                auto tmp = prev(s1.end());
                ans += *tmp;
                s2.insert(*tmp);
                s1.insert(y);
                s1.erase(tmp);
            }
        } else {
            auto it = s1.find(p[x]);
            
            if(y >= *s2.begin()) {
                s2.insert(y);
                ans += y;
                auto tmp = s2.begin();
                s1.insert(*tmp);
                ans -= *tmp;
                s2.erase(tmp);
                s1.erase(it);
            } else {
                s1.erase(it);
                s1.insert(y);
            }
        }

        p[x] = y;
        cout << ans << "\n";
    }

    return 0;
}