글 읽기 - 욱제는 도박쟁이야 질문

lyzqm 6년 전 0

문제를 잘못읽어서 다른 문제를 풀고있었네요...

"동전 배열의 양 끝에서 벗어나서 양 끝의 동전만 뒤집거나 양 끝의 두 개 동전만 뒤집는 것도 가능하다. 동전을 뒤집는 횟수에 제한은 없다."

궁금한게 생겼는데 위의 조건이 없다면 dp로 푸는게 타당할까요?

dp1[idx][a][b][c] : {arr[idx], arr[idx+1], arr[idx+2]}에서 {a,b,c}가 각각 0이면 그대로, 1이면 뒤집는 형식에서의 (최댓값)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N;
int arr1[10001], arr2[10001];
int dp1[10001][2][2][2], dp2[10001][2][2][2];
int solve1(int idx, int fir, int sec, int thi) {
	if (idx == N - 3) {
		int ret = fir == 0 ? arr1[idx] : -arr1[idx];
		ret += sec == 0 ? arr1[idx + 1] : -arr1[idx + 1];
		ret += thi == 0 ? arr1[idx + 2] : -arr1[idx + 2];
		return ret;
	}

	int &ret = dp1[idx][fir][sec][thi];
	if (ret != -1)return ret;
	ret = fir == 0 ? arr1[idx] : -arr1[idx];

	ret += max(solve1(idx + 1, sec, thi, 0), solve1(idx + 1, (sec + 1) % 2, (thi + 1) % 2, 1));
	return ret;
}
int solve2(int idx, int fir, int sec, int thi) {
	if (idx == N - 3) {
		int ret = fir == 0 ? arr2[idx] : -arr2[idx];
		ret += sec == 0 ? arr2[idx + 1] : -arr2[idx + 1];
		ret += thi == 0 ? arr2[idx + 2] : -arr2[idx + 2];
		return ret;
	}
	int &ret = dp2[idx][fir][sec][thi];
	if (ret != -1)return ret;
	ret = fir == 0 ? arr2[idx] : -arr2[idx];

	ret += min(solve2(idx + 1, sec, thi, 0), solve2(idx + 1, (sec + 1) % 2, (thi + 1) % 2, 1));
	return ret;
}
int main() {
	memset(dp1, -1, sizeof dp1);
	memset(dp2, -1, sizeof dp2);
	scanf("%d", &N);
	for (int n = 0;n < N;n++) scanf("%d", &arr1[n]);
	for (int n = 0;n < N;n++) scanf("%d", &arr2[n]);
	int fir = max(solve1(0, 0, 0, 0), solve1(0, 1, 1, 1));
	int sec = min(solve2(0, 0, 0, 0), solve2(0, 1, 1, 1));
	printf("%d\n", fir - sec);
	return 0;
}

vc0612 6년 전 0

어음ㅁ.. 저조건덕분에 그냥 다 절댓값 씌워서 더해주면 되는 쉬운문제가 되어버렸죠....

저 조건이 없다면 절댓값으로 쉽게 푸는게 안되요..!

그래서 저조건이 없다면 간단하게 안되고 어쩔 수 없이 dp로 풀어야해요 ㅠㅁㅠ...

그런데ㅔ... 양끝 두개 동전만?..은 잘모르겠지만 한개 동전만 불가능하게 할경우는

각끝만 뒤집혀 있는 경우만 불가능하니깐 그거 고려해주면, 뭐 dp 없이 if문 두개만 추가해줘서 풀 수 있긴해요.

양끝 두개 동전뒤집기도 불가능하게 하면ㄴ...(생각하기 너무 귀찮은 상태.... 덥다...)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

욱제는 도박쟁이야 질문

lyzqm 6년 전 0

vc0612 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말