-
DP_백준_스티커_9465Algorithm 2018. 8. 16. 15:03
순서가 정해져 있지 않다는것은 우리가 스티커를 때는 순서를 정할 수 있다. 즉 왼쪽부터 한 열씩 스티커를 어떻게 뜯을지를 결정한다. 이 문제 또한 길이가 N 일때 마지막 상태가 정해져 있지 않아서 2차원 배열로 마지막 상태를 표현한다.
1. 정의 : dp[N][M] : 2*N에서 얻을 수 있는 최대점수, M=0(뜯지 않음), M=1(위쪽 스티커를 뜯음), M=2(아래쪽 스티커를 뜯음)
2. 점화식 : dp[N][0] = max(dp[N-1][0], dp[N-1][1], dp[N-1][2])
dp[N][1] = max(dp[N-1][0], dp{n-1][2]) + value[0][N]
dp[N][2] = max(dp[N-1][0], dp[N-1][1]) +value[1][N]
3. 초기화 : 코드참조
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include <iostream>using namespace std;int max(int a, int b, int c) {int tmp = a;if (tmp < b)tmp = b;if (tmp < c)tmp = c;return tmp;}int main() {int count;cin >> count;for (int q = 0; q < count; q++) {int num; // N Lengthcin >> num;int ** value = new int*[2]; //Inputint ** dp = new int*[num]; // DP memoizationfor (int i = 0; i < 2; i++) {value[i] = new int[num];}for (int i = 0; i < num; i++) {dp[i] = new int[3];}//Createfor (int i = 0; i < 2; i++) {for (int j = 0; j < num; j++) {cin >> value[i][j];}}// Inputdp[0][0] = 0;dp[0][1] = value[0][0];dp[0][2] = value[1][0];//Initializefor (int i = 1; i < num; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]);dp[i][1] = max(dp[i - 1][0], dp[i - 1][2], 0) + value[0][i];dp[i][2] = max(dp[i - 1][0], dp[i - 1][1], 0) + value[1][i];}//Calculatecout << max(dp[num - 1][0], dp[num - 1][1], dp[num - 1][2]) << endl;}return 0;}cs 'Algorithm' 카테고리의 다른 글
DP_백준_가장 긴 증가하는 부분 수열_LIS_11053 (0) 2018.08.16 DP_백준_포도주 시식_2156 (0) 2018.08.16 DP_백준_이친수_2193 (0) 2018.08.16 DP_백준_오르막 수_11057 (0) 2018.08.16 DP_백준_쉬운 계단 수_10844 (0) 2018.08.16