글 읽기 - [C++] 20120 질문입니다.

gi5005 3년 전 0

dp이용해서 풀었는데 어디서 놓친 부분이 있는지 모르겠습니다.

DP는 [index][놓친횟수] = {콤보 , 기댓값} 으로 생각해서 풀어봤습니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 5010
#define INF 214748361
// [index][놓친 횟수]
// 콤보 , 최대값
pair<ll,ll> dp[MAX][3];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll N;
	cin >> N;
	ll arr[MAX];
	for(ll i=1;i<=N;i++)
	{
		cin >> arr[i];
	}
	dp[1][1] = {0,0};
	dp[1][0] = {1,arr[1]};
	for(ll i=2;i<=N;i++)
	{
		ll a = (dp[i-1][0].first+1)*arr[i] + dp[i-1][0].second;
		ll b = dp[i-1][1].second;
		ll c = dp[i-1][2].second;

		// 현재 노드를 선택하는 경우
		// 두 노드보다 커질경우
		if(a>=b && a>=c)
		{
			dp[i][0] = {dp[i-1][0].first+1,a};
		}
		// 작을경우 
		else
		{
			dp[i][0] = {1,max(dp[i-1][1].second,dp[i-1][2].second)+arr[i]};
		}

		//노트를 놓치는 경우는 결론적으로 (이전 노드 놓친횟수+1)
		dp[i][1] = {0,dp[i-1][0].second};
		dp[i][2] = {0,dp[i-1][1].second};
	}	
	ll a = dp[N][0].second;
	ll b = dp[N][1].second;
	ll c = dp[N][2].second;
	ll mx = max(c,max(a,b));
	if(mx<=0) mx =0;
	cout << mx;
}

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

문제

문제

출처

ICPC

[C++] 20120 질문입니다.

gi5005 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말