Algoogle

Algorithm for Programming Contest

PA 2010 Mashrooms

Category: PA Tag: greedy, math

Mashrooms

問題概要


きのこが生えてる場所がn個1列に並んでいる.
各位置には個のきのこが生えてる.
きのこは収穫から2単位時間で再び生える.
となりの場所にいくのに1単位時間かかるとき, 時間t以内に最大何個きのこを採れるか.
開始地点は0番目, 終了はどこでも良い.

解法


最適な動きをしているときに戻る場合というのを考える.
戻る場所から進んできているので次も必ず進む.
そこで前に戻っているので次も必ず戻る…
と必ず2箇所でループするはず.

よってそれまでの合計を初めから順に見て各位置でそこからループした場合の合計値を出す.
注意するのはn=1の場合そこに留まり続けるので2回に1回加算されるというのを初期値にしておくこと.

コード


(mashrooms.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;

int n, t, a[1<<20];

long long solve()
{
        long long ans = (1LL*t/2+1)*a[0], sum = a[0], r;
        for (int i = 1; i < n; i++) {
                if(t < i) break;
                r = t-i;
                ans = max(ans, sum+(r+1)/2*a[i-1]+(r/2+1)*a[i]);
                sum += a[i];
        }

        return ans;
}

void input()
{
        scanf("%d%d", &n, &t);
        for (int i = 0; i < n; i++) scanf("%d", a+i);
}

int main()
{
        input();
        printf("%lld\n", solve());
        return 0;
}

Comments