분리와 합체

제목 대의:

n개의 구역이 있는데 그것들을 두 개의 구간으로 나눌 수 있다. 결과에 왼쪽 구간의 가장 왼쪽 구역의 수와 가장 오른쪽 구역의 수, 그리고 오른쪽 구간의 가장 오른쪽 구역의 수를 더하여 이렇게 끊임없이 나누어 결과를 가장 크게 하고 각 경계선의 위치를 출력한다(1/2, 4, 4/8의 순서로)

원제:

제목 설명

기관실에서 수일 동안의 교섭을 통해 LYD는 두신소로부터 분리와 합체를 배웠다. 관문을 통과하기 전에 두신소는 그에게 테스트를 주었다. 두신소는 n개의 구역을 만들었고 그것들은 인접하여 한 줄로 늘어섰다. 번호는 1~n이다.이 구역마다 OI계의 금 열쇠가 놓여 있는데, 하나하나가 모두 일정한 가치가 있으니, LYD는 당연히 그것들을 얻고 싶어한다.그러나 두신우는 LYD가 한꺼번에 모두 가져가지 않고 매번 하나만 가져갈 수 있다고 규정하고 있다.가능한 한 빨리 모든 금 열쇠를 얻기 위해 LYD는 자연히 방금 배운 분리와 합체 기술을 사용했다.처음에 LYD는 1부터 n-1까지의 모든 구역(K로 기재)을 선택하여 들어갈 수 있으며, 들어가면 LYD는 K 구역에서 분리되어 두 개의 작은 LYD로 분리된다.분리가 완료되는 동시에 한쪽 벽이 K와 K+1 구역 사이에 올라가 1부터 k와 k+1부터 n까지 두 개의 독립된 구간으로 차단된다.그리고 두 개의 작은 LYD가 각각 1부터 k+1부터 n까지 들어가서 각자의 구간에서 구간 끝 구역(즉 1부터 k-1 또는 k+1부터 n-1)을 제외한 어느 구역에서 다시 분리를 선택하면 모두 4개의 작은 LYD가 있다... 상기 서술한 분리를 반복한다. 작은 LYD가 자신이 있는 구간에 한 구역만 남았다는 것을 발견할 때까지 그들은 자신이 꿈꾸던 OI금 열쇠를 안을 수 있다.그러나 LYD는 이렇게 n개의 개체로 나누어 세계에 존재할 수 없다. 이런 작은 LYD는 다시 합체하고 합체의 두 작은 LYD가 있는 구간 중간의 벽은 사라진다.합체는 일정한 가치를 얻을 수 있다. 계산 방법은 (합병 후 소재 구간의 좌우단 구역에서 금 열쇠의 가치의 합) 곱하기(전에 분리되었을 때 소재 구역의 금 열쇠 가치)이다.예를 들어 LYD는 13구간 중 2번 구역을 12와 3 두 구간으로 분리한 적이 있으며, 합병할 때 얻은 가치는 (1번 금 열쇠 가치 + 3번 가치)*(2번 금 열쇠 가치)입니다.}LYD는 최종적으로 얻을 수 있는 총 가치가 가장 큰지 프로그래밍해 주세요.그리고 분리 단계의 앞뒤로 왼쪽에서 오른쪽으로 영역이 분리된 영역 번호를 출력합니다. 예를 들어 분리된 영역 번호는 분리된 영역 번호로 출력됩니다. 예를 들어 분리된 영역 번호는 분리된 영역 번호로 인쇄된 후 왼쪽에서 오른쪽으로 분리된 영역 번호로 인쇄됩니다.주의: 여러 가지 방안이 있으면 분리 구역을 최대한 왼쪽으로 하는 방안을 선택하십시오. (출력 사전의 순서가 가장 작은 것으로 이해할 수도 있습니다.)

입력

첫 번째 줄: 정수 n(2<=n<=300) 두 번째 줄: n개의 정수는 1~n 구역에서 금 열쇠의 가치를 나타낸다.답안 및 연산 과정 중longint 범위를 초과하지 않도록 보증합니다.

출력

첫 번째 줄은 하나의 수, 즉 얻은 최대 가치이다. 두 번째 줄은 분리 단계의 앞뒤로 구역이 왼쪽에서 오른쪽으로 순서대로 분리된 구역 번호를 출력하고 중간은 하나의 공백으로 구분한다. 만약에 여러 가지 방안이 있다면 분리 구역을 최대한 왼쪽으로 하는 방안을 선택한다.

샘플 가져오기

7
1 2 3 4 5 6 7

샘플 내보내기

238
1 2 3 4 5 6

설명

데이터 범위 규약

%20의 데이터 N<=10 대 40의 데이터 N<=50 대 100의 데이터 N<=300 a[i]<=300

문제 해결 방법:

자갈을 합쳐서 고치고, 덧붙인 수를 제목으로 바꾸고, 그 다음에 출력 경계선으로 귀속시킨다

코드:

#include
#include
#include
using namespace std;
int n,k,t,a[305],f[305][305],b[305][3055];
void dg(int x,int y,int dep)
{
	if (x>=y) return;// 
	if (dep==k)// 
	  {
	  	printf("%d ",b[x][y]);// 
	  	t=1;// 
	  	return;
	  }
	dg(x,b[x][y],dep+1);// 
	dg(b[x][y]+1,y,dep+1);// 
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	  scanf("%d",&a[i]);
	for (int i=n-1;i>0;--i)// 
	  for (int j=i+1;j<=n;++j)
	    for (int c=i;c<j;++c)
	      if(f[i][c]+f[c+1][j]+(a[i]+a[j])*a[c]>f[i][j])// 
	        {
	        	f[i][j]=f[i][c]+f[c+1][j]+(a[i]+a[j])*a[c];
	        	b[i][j]=c;// 
	        }
	printf("%d
",f[1][n]);
	t=1;
	while(t)
	{
		t=0;// 
		k++;// 
		dg(1,n,1);
	}
}