ABC125-D : Flipping Signs

작성일

https://atcoder.jp/contests/abc125/tasks/abc125_d

  • 흔한 2개 선택중 하나 고르는 DP, 실수해서 계속 Segmentation Fault가 남
  • 정신 똑바로 처리기
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef long long LL;
LL flippingSign(int N, vector<int>& A) {
	vector<vector<LL>> dp(2, vector<LL>(N));
	
	dp[0][0] = A[0];
	dp[1][0] = -A[0];
	
	for(int i = 1; i < N-1; i++) {
		dp[0][i] = max( dp[0][i-1] + A[i], dp[1][i-1] - A[i]);
		dp[1][i] = max( dp[0][i-1] - A[i], dp[1][i-1] + A[i]);
	}
	return max(dp[0][N-2] + A[N-1], dp[1][N-2] - A[N-1]);
}