글 읽기 - 고수님들 어디가 틀린지 봐주십쇼

rrnjs0721 4년 전 0

11053, 14002 풀때 썻던 dp를 가지고 이어서 만들었습니다.

첫번째 주석 이후가 새로 만든건데 게시판 다시 뒤져보면서 생각할만한 반례는 모두 넣어봤는데 맞는 것 같습니다.

어디가 틀린건지 한 번 봐주십쇼...

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main(void){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int N;
	cin>>N;
	int arr[N+1] = {0};
	int dp[N+1] = {0};
	for(int i=1;i<=N;i++)
		cin>>arr[i];
	dp[1] = 1;
	int mmax = 1;
	for(int i=2;i<=N;i++){
		int cnt = 0;
		for(int j=1;j<i;j++){
			if(arr[i] > arr[j]){
				if(cnt < dp[j])
					cnt = dp[j];
			}
			dp[i] = cnt+1;
			if(mmax < dp[i])
				mmax = dp[i];
		}
	} // 14002와 11053 풀때 썼던 dp
	int arr_sum[N+1]={0}; //합을 저장하는 배열
	for(int i=1;i<=N;i++){
		int max_sum=0;
		for(int j=0;j<i;j++){
			if(dp[j] == dp[i]-1 && arr[j] < arr[i]){
				int temp = arr_sum[j];
				max_sum = max(max_sum,temp);
			} // dp가 1작고 arr[i]보다 작은 수의 arr_sum[j]중에 큰값을 max_sum에 저장
		}
		arr_sum[i] = arr[i] + max_sum; // arr_sum[i] 구하기
	}
	int result=0;
	for(int i=1;i<=N;i++)
		result = max(result,arr_sum[i]); // 한번 쭉 돌면서 제일 큰 값출력
	cout<<result<<endl;
}

djm03178 4년 전 0

길이가 가장 긴 것 중에서 최대를 골라야 하는 게 아닙니다. 길이와는 관계 없이 합이 가장 크기만 하면 됩니다.

https://ideone.com/Fc5QrH

rrnjs0721 4년 전 0

문제를 잘못 이해했군요 감사합니다!

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

문제

문제

출처

ICPC

고수님들 어디가 틀린지 봐주십쇼

rrnjs0721 4년 전 0

djm03178 4년 전 0

rrnjs0721 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말