mayoko’s diary

プロコンとかいろいろ。

京都大学プログラミングコンテスト2015 D - 高橋君の旅行

KUPC2015 に参加しました。
ABCDE 解いて 60 位くらいでした。うーん。

解法

方針としては, 最後に滞在する街で場合分けしてそれぞれの場合に得られるお金の最大値を求める, という感じで解きます。

そのためには, 街 i に滞在するために最低限必要な日数, およびその際に持っているお金を dp で持っておけば良いです。
街 i で滞在するときに稼げるお金は, 街 0 から i の中で滞在する際にもらえるお金の最大値とみなせることに注意します。

なんとなく 今年の ICPC 国内予選の D 問題に似てると思いました(pair の値を dp する感じが)。

const int MAXN = 100010;
ll A[MAXN], B[MAXN];
pair<ll, ll> dp[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> B[i];
    }
    for (int i = 1; i <= N; i++) {
        B[i] = max(B[i], B[i-1]);
    }
    for (int i = 0; i <= N; i++) {
        dp[i].first = MAXN;
    }
    dp[0] = make_pair(0ll, 0ll);
    for (int i = 1; i <= N; i++) {
        ll rest = A[i-1] + dp[i-1].second;
        if (rest >= 0) {
            dp[i].first = dp[i-1].first+1;
            dp[i].second = rest;
            continue;
        }
        ll need = -rest;
        if (B[i-1] == 0) {
            break;
        }
        ll day = need/B[i-1];
        if (need%B[i-1]) day++;
        if (day > MAXN) break;
        dp[i].first = dp[i-1].first+day+1;
        //dp[i].second = dp[i-1].second + day*B[i-1] - need;
        dp[i].second = dp[i-1].second + day*B[i-1] + A[i-1];
    }
    ll ans = 0;
    for (int i = 0; i <= N; i++) {
        if (dp[i].first > N) break;
        ans = max(ans, dp[i].second + (N-dp[i].first)*B[i]);
    }
    cout << ans << endl;
    return 0;
}