[AOJ] No. 0340 パンケーキ

2019年12月27日2020年12月18日

問題

方針

両端のパンケーキは \( 1 \) 枚だけ裏返すことができることに着目します。左端のパンケーキは単独で裏返す回数を \( k \) とすると、最小値を達成するためには、\( 0 \leq k \leq p_1 \) であることが分かります。ここで、\( k \) 回左端のパンケーキを単独で裏返した場合、\( p_1 \leftarrow p_1 – k \) と値を更新します。次に、\( 2 \) 枚同時に裏返すので、パンケーキの裏返す回数は、\( 2p_1 \) 増加し、\( p_2 = \max(0, p_2 – p_1) \) となります。次に、左から \( 2 \) 個目のパンケーキと \( 3 \) 個目のパンケーキを裏返すので、\( 2p_2 \) となり、\( p_3 = \max(0, p_3 – p_2) \) となります。この操作を \( N – 1 \) まで繰り返し、\( p_N \) 回単独で右端のパンケーキを裏返すことになります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int p[N];
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    int ans = INT32_MAX;
    int a[N];
    for (int i = 0; i <= p[0]; i++) {
        for (int j = 0; j < N; j++) a[j] = p[j];
        int t = i;
        a[0] -= i;
        for (int j = 0; j < N - 1; j++) {
            t += 2 * a[j];
            a[j + 1] = max(0, a[j + 1] - a[j]);
        }
        t += a[N - 1];
        ans = min(ans, t);
    }
    cout << ans << "\n";
    return 0;
}

感想

解説を見てまさか全探索だとは思いませんでした。