読者です 読者をやめる 読者になる 読者になる

Codeforces #216 Div2 D. Valera and Fools

ただの幅優先探索です。たまには簡単な問題も。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <queue>
#include <stack>
#include <tuple>

using namespace std;


typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const int MAX_N = 3010;
int n, k;
int p[MAX_N], kill[MAX_N];
bool dp[MAX_N+1][MAX_N+2] = {};

int main(int argc, char *argv[]) {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int d;
        scanf("%d", &d);
        if (d == 0) p[i] = 1;
        else if (d == 100) p[i] = 2;
        else p[i] = 3;
    }
    p[n] = 0;
    for (int i = n-1; i >= 0; i--) {
        if (p[i] == 2 || kill[i+1] == 2) {
            kill[i] = 2;
        } else {
            kill[i] = max(kill[i+1], p[i]);
        }
    }

    queue<T> q;
    q.push(T(0, 1, k));
    int res = 0;
    while (!q.empty()) {
        T t = q.front(); q.pop();
        int a = get<0>(t), b = get<1>(t), c = get<2>(t);
        if (b > n+1) continue;
        if (dp[a][b]) continue;
        dp[a][b] = true;
        res += 1;
        if (!c) continue;

        if (kill[b] & 0x01) {
            if (p[a] & 0x01) {
                q.push(T(a, b, c-1));
            }
            if (p[a] & 0x02) {
                q.push(T(a, b+1, c-1));
            }
        }
        if (kill[b] & 0x02) {
            if (p[a] & 0x01) {
                q.push(T(b, b+1, c-1));
            }
            if (p[a] & 0x02) {
                q.push(T(b+1, b+2, c-1));
            }
        }
    }
    cout << res << endl;
    return 0;
}