mayoko’s diary

プロコンとかいろいろ。

JAG Practice Contest for ACM-ICPC Asia Regional 2015 C - Delete Files

解法

長さが短いものから順に処理していきます。
処理するときは, その手前のファイル, それより後のファイルをどれだけ消せるかを確かめていけば良いです。

要するに貪欲法ですが, 小さい順に消していけば, 「消せるものは消すべき」という戦略が必ず正しいのでこれで良いです(この順序じゃないと, 小さいのを消すのを優先したせいで消せるはずだったものが消せなくなるなどして損になる可能性がある)。

const int MAXN = 1010;
char D[MAXN];
int L[MAXN];

pii P[MAXN];
bool used[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> D[i] >> L[i];
        P[i].first = L[i];
        P[i].second = i;
    }
    sort(P, P+N);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int len = P[i].first;
        int id = P[i].second;
        if (used[id] || D[id] == 'n') continue;
        ans++;
        used[id] = true;
        for (int j = id-1; j >= 0; j--) {
            if (D[j] == 'n' && len <= L[j]) break;
            used[j] = true;
        }
        for (int j = id+1; j < N; j++) {
            if (D[j] == 'n' && len <= L[j]) break;
            used[j] = true;
        }
    }
    cout << ans << endl;
    return 0;
}