ABC464 D - Celester

考え方

最終日の最大嬉しさをいきなり求めようとしても、とても大変。
天気を変えるか変えないかの $2$ 択を $N$ 回やるので、計算量が $O(2^N)$ になってしまう。

しかし、最終日の $1$ 日前についての必要な情報が得られたら、簡単に答えが出せる。
最終日前が晴だった場合の中での最大嬉しさと、同じく雨だった場合のデータがあればよい。

最終日が晴になる方として、晴→晴はそのまま、雨→晴の方には $Y$ の値を足す。
そのうち大きい方を採用する。
最終日が雨になる方として、晴→雨はそのまま、雨→雨もそのまま。
そのうち大きい方を採用する。
その後、元の天気と異なる方からは $X$ の値を引く。
そして、最終日が晴の場合と雨の場合のうち、嬉しさが大きい方を答えればよい。

これで最終日の $1$ 日前の情報から最終日の答えを $O(1)$ で求めることができる。
そしてこの方法は、最終日以外でも前日の答えを利用して毎日の答えを $O(1)$ で求めるのに使える。
よって、動的計画法で日付順に $1$ 日ずつ求めていけば $O(N)$ で最終日の答えが出せる。

入力例1での動作

$1$ つめのテストケースのみ。

入力を受け取る。

q: 5
n: 6
s: "SRRRSR"
x: {3, 1, 4, 1, 5, 9}
y: {2, 6, 5, 3, 5}

以下では、日付と配列の添字を 0-indexed で扱う。
各日について、以下の $2$ つを持つ。

• その日を晴で終える場合の最大嬉しさ
• その日を雨で終える場合の最大嬉しさ

$0$ 日目の元の天気は晴である。
そのまま晴にする場合の嬉しさは $0$、雨に変える場合は $X_0=3$ だけ減るので $-3$ となる。

$1$ 日目の元の天気は雨である。
晴にする場合は、前日の天気ごとに次の値になる。

• 前日が晴なら $0$
• 前日が雨なら $-3+2=-1$

大きい方の $0$ を選んでから $X_1=1$ を引くので、$-1$ となる。
雨にする場合は、前日の $0$ と $-3$ の大きい方を引き継ぐので $0$ となる。

$2$ 日目の元の天気も雨である。
晴にする場合は、前日の天気ごとに次の値になる。

• 前日が晴なら $-1$
• 前日が雨なら $0+6=6$

大きい方の $6$ を選んでから $X_2=4$ を引くので、$2$ となる。
雨にする場合は、前日の $-1$ と $0$ の大きい方を引き継ぐので $0$ となる。

同様に最後まで処理すると、各日の最大嬉しさは次のようになる。

最後の日は晴でも雨でもよいので、$-4$ と $5$ の大きい方を選ぶ。
したがって、このテストケースの答えは $5$ となる。

注意点

嬉しさの合計値は、int 型からはみ出る。
long long 型を用いること。

別解

特になし。