ABC125 D - Flipping Signs

D - Flipping Signs

概要

N項の数列Aが与えられる。「1からN-1までの番号iを選び、A[i-1]とA[i]に-1を乗算する」という操作を好きなだけ行う。操作終了後の数列をBとするとき、Bの和の最大値を求めよ。

制約

2 ≦ N ≦ 10^5
-10^9 ≦ A[i] ≦ 10^9

方針①

いろいろ実験を行うと、任意の偶数個の項の符号を反転させられることが分かる。
なので、負の数が偶数個ならそれらをすべてプラスにすればよい。負の数が奇数個なら、絶対値が最も小さい項の符号をマイナスとし、それ以外の項の符号をプラスにすればよい。

解答①

Submission #5160616 - AtCoder Beginner Contest 125

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<ll> A(N);
	rep(i, N) cin >> A[i];
 
	ll INF = 1e13;
	ll mn = INF;
	ll mx = -INF;
	int cnt = 0;
	rep(i, N){
		if(A[i] < 0){
			mx = max(mx, A[i]);
			cnt++;
		}else{
			mn = min(mn, A[i]);
		}
	}
 
	ll ans = 0;
	if(cnt % 2 == 0){
		rep(i, N){
			ans += abs(A[i]);
		}
 
		cout << ans << endl;
	}else{
		rep(i, N){
			ans += abs(A[i]);
		}
 
		if(mn != INF){
			ans += mx;
			ans -= mn;
			ans -= min(abs(mx), abs(mn));
			ans += max(abs(mx), abs(mn));
		}else{
			ans += 2 * mx;
		}
 
		cout << ans << endl;
	}
}

方針②

DPで計算する。
もし任意の項の正負を逆転させられるのであれば、直前の項までの最大値を保持しておけばよいのだが、この問題は隣接2項の符号を同時に変えるため、特に最後の項の符号はその1項前の符号反転の有無に依存することになる。そのため直前の項までの最大値の情報に加え、その項で符号を反転させているかどうかの情報も必要となる。

よって下記のようにDPを定義する。
dp[i][j]：i番目までの項までの和の最大値、j=0ならi番目で(i, i+1)番目の符号を反転させていない、j=1ならi番目で(i, i+1)番目の符号反転させている
すると、このDPは下記のように遷移する。
dp[0][0] = 0
dp[0][1] = -INF
dp[i+1][0] = max(dp[i][0] + A[i], dp[i][1] - A[i])
dp[i+1][1] = max(dp[i][0] - A[i], dp[i][1] + A[i])
最終的な解答はdp[N][0]である。（前述のとおりN番目の項では符号反転できないことに注意）

遷移のイメージは下記の通り。（A[i]はi+1番目の項であることに注意）
dp[i][0] → dp[i+1][0]：i番目の項で(i, i+1)番目の符号を反転させておらず、かつi+1番目の項でも符号を反転させないため、A[i]は加算される
dp[i][1] → dp[i+1][0]：i番目の項で(i, i+1)番目の符号を反転させており、かつi+1番目の項では符号反転させないため、A[i]は減算される
dp[i][0] → dp[i+1][1]：i番目の項で(i, i+1)番目の符号を反転させておらず、かつi+1番目の項で符号を反転させるため、A[i]は減算される
dp[i][1] → dp[i+1][1]：i番目の項で(i, i+1)番目の符号を反転させており、かつi+1番目の項でも符号反転させるため、A[i]は加算される

解答②

Submission #5169270 - AtCoder Beginner Contest 125

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<ll> A(N);
	rep(i, N) cin >> A[i];
 
	vector<vector<ll>> dp(N+1, vector<ll>(2, 0));
 
	dp[0][1] = INT_MIN;
	for(int i = 1; i <= N; i++){
		dp[i][0] = max(dp[i-1][0] + A[i-1], dp[i-1][1] - A[i-1]);
		dp[i][1] = max(dp[i-1][0] - A[i-1], dp[i-1][1] + A[i-1]);
	}
 
	cout << dp[N][0] << endl;
}