글 읽기 - 구간 나누기 점화식 이거 맞나요?

QuqqU 6년 전 0

dp[i][j] : i번째수가 j번째 구간의 마지막 수일때의 최적값

으로 정의하고,

i번째 수가 들어올 차례에,

(j. ==. 0 ~ i -2)

dp[i][1~m] = dp[j][0~m-1] + ((( j+1부터 i까지의 원소의 합(하나의 구간 취급) )))

으로 dp를 계산해주고,

dp[1~i][m]을 순회하면서 최대값을 뽑아내려했는데,

어디가 잘못됬나요??

#include <iostream>
#include <algorithm>
using namespace std;
int dp[105][55];//i번째수/j번째구간
int arr[105];
int main () {
	for(int i=0;i<105;i++)
		for(int j=1;j<55;j++)
			dp[i][j]=arr[i]=-999999999;
    
	int n,m; scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    
	dp[1][1]=max(arr[0],arr[1]);
	dp[0][1]=arr[0];
    
	for(int i = 2; i < n; i++){
		int aa=0;
		for(int j = i-2; j >= 0; j--){
			aa += arr[j+2];
			for(int k = 0; k < m; k++)
				dp[i][k+1] = max(dp[i][k+1], dp[j][k] + aa);
		}
	}

    
    
	int ans=-999999999;
	for(int i =0;i<n;i++)
		ans=max(ans, dp[i][m]);
	if(n==1)printf("%d\n",arr[0]);
	else if(n==2)printf("%d\n",max(arr[0],arr[1]));
	else printf("%d\n", ans);
	


	return 0;
}

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

문제

문제

출처

ICPC

구간 나누기 점화식 이거 맞나요?

QuqqU 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말