题解 P2418 【yyy loves OI IV】

acesrc · 2018-04-03 21:43:05 · 题解

emmmm. 第一眼就觉得这道题应该, 除了最后一个宿舍, 其余宿舍要么全是1要么全是2, 要么1和2的数量的绝对值应该"等于"m. 所以用一个前缀和直接DP就O(n)了? 不用前面的题解那些树结构. 这题的数据有点弱, 所以也不太保证程序是对的.

#include <iostream>
#include <algorithm>
#include <map>
#include <cstdio>
#include <unordered_map>
using namespace std;

const int maxn = 500000 + 7;
int n, m;
int data[maxn], f[maxn], s1[maxn], s2[maxn];

unordered_map<int, int> mp;
void update(int u, int x) {
    if (mp.count(u) == 0) {
        mp[u] = x;
    }
    else mp[u] = min(mp[u], x);
}

const int inf = 2147483646;
int query(int u) {
    if (mp.count(u) == 0) return inf;
    return mp[u];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &data[i]);
    }
    for (int i = 1; i <= n; i++) {
        s1[i] += s1[i - 1] + (data[i] == 1);
        s2[i] += s2[i - 1] + (data[i] == 2);
    }
    int last1 = 0, last2 = 0;
    f[0] = 0;
    update(0, 0);
    for (int i = 1; i <= n; i++) {
        if (data[i] == 1) {
            f[i] = f[last2] + 1;
            last1 = i;
        }
        else if (data[i] == 2) {
            f[i] = f[last1] + 1;
            last2 = i;
        }
        f[i] = min(f[i], min(query((s1[i] - s2[i]) - m), query((s1[i] - s2[i]) + m)) + 1);
        update(s1[i] - s2[i], f[i]);
    }

    int ans = inf;
    if (abs(s1[n] - s2[n]) <= m) ans = 1;
    else {
        for (int i = 1; i <= n; i++) {
            if (s2[n] - s2[i] == 0) ans = min(ans, f[i] + 1);
            if (s1[n] - s1[i] == 0) ans = min(ans, f[i] + 1);
            if (abs((s1[i] - s2[i]) - (s1[n] - s2[n])) <= m) ans = min(ans, f[i] + 1);
        }
    }
    cout << ans << endl;
    return 0;
}