YukicoderContest287 B問題P2 「Two color sequence」
https://gyazo.com/83df7a2ec990e4b4f64f261c77fc730d
問題概要
制約
$ N \leq 2 \times 10^5
解法・お気持ち
$ |R - B|を求める必要があり、どのように解くか悩みました。
このままだと$ O(N^2)かかってしまいます。
ここで、絶対値でよく出てくる公式を考えました。
これは、どうみても絶対値をうまく使うことで解ける問題そう...と考えたためです。
その公式は過去問でよく出てくる$ |x| = \max(x, -x)です。
これを当てはめると
$ |R-B| = \max(R - B, B - R)になります。
$ R - Bは、$ Rを最大化して、$ Bを最小化すればいいです。
$ B - Rは、$ Bを最大化して、$ Rを最小化すればいいです。
そう考えてうーんわからないですね、になりましたが、もう少し考えました。
$ Xを最大化、$ Yを最小化するときこれらは独立に考えることができます。
$ Xはそのまま和を最大化する気持ちです。
問題は$ Yを最小化することです。
これは$ Yの正負を逆にすると、最大化と等しくなる、と考えました。
よって、赤色を正に最大化したいときは、青色の値をすべて*−1して正負を逆にします。
するとあとはこの修正した系列$ a'の最大の部分列を求めれば良くなります。これはDPをすればよいです。
青色を正に最大化したいときは、赤色を同様に*−1すればよいです。
よって、あとは最大の部分列をするDPフェーズになります。
これはdp[i+1] = max(a[i], dp[i] + a[i])です。
dp[i] = i番目のa_iを 必ず 使うとしたときに、作ることのできる最大の値 とします。
すると、$ i番目を見るときは、「自分自身のみ」を使うか、「i-1番目までの最大の作り方 に自分自身$ a_iを足すか」を使うか のどちらかなので解くことができます。
AOJに確かあった気がしています。
計算量
$ O(N)
新たな学び
最小化は、正負を逆にすると最大化になる
独立を考える
反省点
コード
code: cpp
LL f(int N, const vector<LL> a) {
vector<LL> dp(N + 1, 0);
for (int i = 0; i < N; i++) {
}
return *max_element(dp.begin(), dp.end());
}
int main() {
int N;
cin >> N;
string S;
cin >> S;
vector<LL> a(N);
cin >> a;
vector<LL> b = a, c = a;
for (int i = 0; i < N; i++)if (Si == 'R') bi *= -1; for (int i = 0; i < N; i++)if (Si == 'B') ci *= -1; cout << max(f(N, b), f(N, c));
}