interval/권영기

결과 ¶

run-id user id 프로그램 명 결과 언어 경과 시간(초) 코드 사이즈(byte) 제출 시간
1371369 zeropage interval accept C++ 0.05 1404 2014-07-15 19:59

풀이 ¶

http://183.106.113.109/30stair/interval_doc/interval_doc.php?pname=interval_doc
점화식에 대한 설명은 위에 잘 나와있다.
문제에서는 interval의 합과 더불어 추가적으로 어떻게 구간을 나눴는지 물어본다.

DP 테이블 말고 다른 2차원 테이블을 하나 추가적으로 두어(P라고 하자), 어느 위치에서 구간을 나눴는지를 표시한다. 예를 들면 P(0, 9) = 4라면, 구간을 (0 ~ 4)와 (5 ~ 9)로 나눴다는 것. 이렇게 해서 나눠지지 않은 구간이 될 때까지 찾는다. 재귀 쓰세요.

소스 ¶


#include<iostream>
#include<queue>
using namespace std;
const int size = 120;
int n, seq[size];
int d[size][size], p[size][size];
queue < int > intervalQueue;
void findInterval(int s, int e, int* nOfInterval){
	if(p[s][e] == -1){
		intervalQueue.push(e - s + 1);
		return;
	}
	else{
		findInterval(s, p[s][e], nOfInterval);
		findInterval(p[s][e] + 1, e, nOfInterval);
		(*nOfInterval)++;
	}
}
int main(void){

	cin>>n;
	for(int i = 0; i<n; i++){
		cin>>seq[i];
	}

	for(int interval = 1; interval <= n-1; interval++){
		for(int x = 0; x < n - interval; x++){
			int y = x + interval, max = 0, min = 999999, intervalValue, intervalPos = -1;
			
			
			for(int k = x; k <= y; k++){
				if(max < seq[k])max = seq[k];
				if(min > seq[k])min = seq[k];
			}
			intervalValue = max - min;
			//find intervalValue between xth and yth. only 1 interval.
			if(x + 1 < y - 1){
				for(int k = x + 1; k < y - 1; k++){
					if(intervalValue < d[x][k] + d[k+1][y]){
						intervalValue = d[x][k] + d[k+1][y];
						intervalPos = k;
					}
				}
			}
			//find intervalValue between xth and yth by using DP table. available more than 1 interval.
			d[x][y] = intervalValue;
			p[x][y] = intervalPos;
		}
	}
	//we only consider upper triangle of DP table. y is always greater than x.

	int intervalSum = d[0][n-1], intervalNum = 1;
	findInterval(0, n-1, &intervalNum);
	cout<<intervalSum<<endl;
	cout<<intervalNum<<endl;
	while(!intervalQueue.empty()){
		cout<<intervalQueue.front()<<" ";
		intervalQueue.pop();
	}

	return 0;
}