U476174 DP 必刷题 #1

wqq

你得到了超级大奖，需要参加一个游戏决定自己的奖金。 有 $n$ 个东西会依次从你身边滑过，第 $i$ 个物品的奖金是 $a_i$，你可以选择拿或不拿一个物品。 设你手中选择已经有了 $j$ 个物品，当前你面前滑过的是第 $i$ 个物品，若你选择要拿： - 当 $(j+1)$ 是 $3$ 的倍数时，得到的奖金是 $3a_i$。 - 否则得到的奖金是 $a_i$。 问你能得到的最大奖金。

一行，一个正整数 $n$。 一行，共 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

一行，一个正整数，表示答案。

对于 $20\%$：$1 \le n \le 10,1 \le a_i \le 5$。 对于另外的 $80\%$：$1 \le n \le 10^5,1 \le a_i \le 10^9$。