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}

dp_s[i] を、$i$ 日目の天気を晴にしたときの、$i$ 日目までの嬉しさの最大値とする。
dp_r[i] を、$i$ 日目の天気を雨にしたときの、$i$ 日目までの嬉しさの最大値とする。
（ただし、日付は 0-indexed で扱っている）

dp_s: {0, 0, 0, 0, 0, 0}
dp_r: {0, 0, 0, 0, 0, 0}

$0$ 日目を処理する。
元の天気は晴なので、雨に変える場合だけ嬉しさが $3$ 減る。

dp_s: {0, 0, 0, 0, 0, 0}
dp_r: {-3, 0, 0, 0, 0, 0}

$1$ 日目を処理する。
晴れる場合、前日が雨の場合に嬉しさ $2$ を加えても、前日晴だった場合の嬉しさより劣る。
したがって、晴れる場合の最大嬉しさは $0$。
雨の場合、前日の嬉しさが大きい方を引き継いで、最大嬉しさは $0$。
そこから、元の天気は雨なので、晴に変える場合だけ嬉しさが $1$ 減る。

dp_s: {0, -1, 0, 0, 0, 0}
dp_r: {-3, 0, 0, 0, 0, 0}

$2$ 日目を処理する。
晴れる場合、前日が雨の場合に嬉しさ $6$ を加えると、前日晴だった場合の嬉しさに勝る。
したがって、晴れる場合の最大嬉しさは $6$。
雨の場合、前日の嬉しさが大きい方を引き継いで、最大嬉しさは $0$。
元の天気は雨なので、晴に変える場合だけ嬉しさが $4$ 減る。

dp_s: {0, -1, 2, 0, 0, 0}
dp_r: {-3, 0, 0, 0, 0, 0}

$3$ 日目から $5$ 日目までを同様に処理する。

dp_s: {0, -1, 2, 4, 5, -4}
dp_r: {-3, 0, 0, 2, -1, 5}

最後の日の天気はどちらでもよいので、dp_s[n-1] と dp_r[n-1] の大きい方が答えである。

result: 5

注意点

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

別解

特になし。