에너지 목걸이 (구간 DP, 링 모양)

Mars 별 에 서 는 모든 Mars 사람들 이 에너지 목 걸 이 를 차고 있다.목걸이 에 N 개의 에너지 구슬 이 있다.에너지 볼 은 머리 표시 와 꼬리 표시 가 있 는 구슬 로 이 표 시 는 특정한 정수 에 대응 하고 있다.그리고 인접 한 두 개의 구슬 에 대해 앞의 구슬 의 꼬리 표 시 는 반드시 뒤의 구슬 의 머리 표시 와 같다.그래 야 흡 판 (흡 판 은 Mars 인 이 에 너 지 를 흡수 하 는 기관) 의 작용 을 통 해 이 두 구슬 이 하나의 구슬 로 모여 흡 판 에 흡수 될 수 있 는 에 너 지 를 방출 할 수 있 기 때문이다.만약 에 앞의 에너지 구슬 의 머리 가 m 로 표시 되 고 꼬리 는 r 로 표시 되 며 뒤의 에너지 구슬 의 머리 는 r 로 표시 되 고 꼬리 는 n 으로 표시 되면 취 합 된 후에 방출 되 는 에 너 지 는 (Mars 단위) 이 고 새로 생 긴 구슬 의 머리 는 m 로 표시 되 며 꼬리 는 n 으로 표시 된다.
필요 할 때 Mars 사람들 은 빨판 으로 인접 한 두 개의 구슬 을 끼 워 넣 고 중합 을 통 해 목걸이 에 구슬 이 하나 밖 에 남지 않 을 때 까지 에 너 지 를 얻는다.분명 한 것 은 서로 다른 집합 순서 로 얻 은 총 에 너 지 는 다 릅 니 다. 집합 순 서 를 설계 하여 목걸이 가 방출 하 는 총 에 너 지 를 가장 크게 만들어 주 십시오.
예 를 들 어 N = 4, 4 개의 구슬 의 머리 표시 와 꼬리 표 시 를 설정 하면 (2, 3) (3, 5) (5, 10) (10, 2) 순 으로 한다.우 리 는 기호 8853 으로 두 개의 구슬 의 집적 작업 을 나타 내 고 (j * 8853 ° k) 는 제 j, k 두 개의 구슬 이 집적 한 후에 방출 되 는 에 너 지 를 나타 낸다.4 번, 1 번 두 개의 구슬 이 합 쳐 진 후에 방출 되 는 에 너 지 는 다음 과 같다.
(4⊕1)=10*2*3=60。
이 목 걸 이 는 가장 좋 은 집합 순 서 를 얻 을 수 있 습 니 다. 총 에 너 지 는?
((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。
 
[파일 입력]
파일 energy. in 을 입력 하 는 첫 줄 은 정수 N (4 ≤ N ≤ 100) 으로 목걸이 에 있 는 구슬 의 개 수 를 표시 합 니 다.두 번 째 줄 은 N 개의 빈 칸 으로 격 리 된 정수 로 모든 수가 1000 을 넘 지 않 는 다.i 개 수 는 i 번 째 구슬 의 머리 표기 (1 ≤ i ≤ N) 이 며, i < N 시 i 번 째 구슬 의 꼬리 표 시 는 i + 1 번 구슬 의 머리 표기 와 같 아야 한다.N 번 째 구슬 의 꼬리 표 시 는 1 번 째 구슬 의 머리 표시 와 같 아야 한다.
구슬 의 순 서 는 이렇게 확정 할 수 있다. 목 걸 이 를 탁자 위 에 올 려 놓 고 교차 하지 말고 첫 번 째 구슬 을 마음대로 지정 한 다음 시계 방향 으로 다른 구슬 의 순 서 를 정할 수 있다.
[출력 파일]
출력 파일 energy. out 은 한 줄 만 있 고 정수 E (E ≤ 2.1 * 109) 로 가장 좋 은 집합 순서 로 방출 되 는 총 에너지 입 니 다.
[샘플 입력]
4
2  3  5  10
[출력 사례]
710
[문제 분석]
이 문 제 는 이번 시험의 점수 문제 라 고 할 수 있 는데, 대부분의 선수 들 이 이 문 제 를 풀 었 다.하지만 대부분의 사람들 은 간단 하 다 고 생각한다.사실 그것 은 전형 적 인 돌 이 합 쳐 진 변형 이다.
(1) 표준 알고리즘
이 문제 의 시험 포 인 트 는 구간 상의 동적 계획 이 어야 한다. 이 문 제 를 생각 하기 전에 목걸이 의 고리 모양 을 어떻게 처리 해 야 할 지 생각해 야 한다.제목 에 따라 우 리 는 절단 점 을 매 거 하여 고리 모양 을 체인 모양 으로 처리 할 수 있다.물론 더 좋 은 방법 은 고 리 를 임 의적 으로 자 르 고 두 개의 체인 으로 복사 하여 이 두 개의 체인 의 머리 와 꼬리 를 연결 하 는 것 이다. 문제 에 대한 읽 기 는 우리 가 직접 읽 은 데 이 터 를 복사 한 후에 연결 하면 된다.
2 3 510      ----------->2 3 5 10 2 3 5 10
이렇게 처리 한 후에 그 중의 임 의 길이 가 N + 1 인 체인 은 하나의 링 을 대표 할 수 있다. 그러면 문 제 는 임 의 길이 가 N + 1 인 체인 을 합병 하여 방출 할 수 있 는 총 에너지 가 가장 크다.
즉, 임의의 점 (i < k < j) 에서 체인 을 두 단락 으로 뜯 는 문제 의 해답 은 이 두 단락 을 합병 하여 최대 에 너 지 를 방출 하 는 것 이다. 게다가 합병 후 이 두 구슬 이 다시 합 쳐 방출 하 는 에 너 지 를 방출 하 는 것 이다.이 문 제 를 한층 더 분해 하 는 것 은 체인 길이 가 1, 즉 두 과목 의 구슬 이 있 을 때 이 두 기둥 을 생 성하 여 에 너 지 를 방출 하지 않 고 그들 이 방출 하 는 에 너 지 를 합병 하 는 것 이다.(이것 이 경계 조건 이다).
우 리 는 하나의 상태 opt [i, j] 를 설계 하여 합병 머리 는 i 이 고 꼬리 는 j 의 체인 목걸이 가 방출 할 수 있 는 가장 많은 에너지 값 을 표시 합 니 다.경계 조건 은 opt [i, i] = 0 (1 < = i < = n * 2) 입 니 다.
정의 에 따라 동 규 의 상태 전이 방정식 을 얻 기 어렵 지 않 습 니 다.
opt[i,j]=max{opt[i,j],opt[i,k]+opt[k,j]+a[i]*a[k]*a[j]}(i#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; int n, dp[100][101], a[210][3]; int main() { while(scanf("%d",&n) != EOF) { int i, j, k; for(i = 0; i < n; i++) { scanf("%d",&a[i][0]); if(i > 0) a[i-1][1] = a[i][0]; } a[n-1][1] = a[0][0]; a[0][1] = a[1][0]; for(i = 0; i < n; i++) { a[i+n][0] = a[i][0]; a[i+n][1] = a[i][1]; } for(k = 0; k < n; k++) { for(i = 0; i < 2 * n; i++) { for(j = i ; j < i + k; j++) { int tmp = dp[i][j] + dp[j+1][i+k] + a[i][0] * a[j][1] * a[i+k][1]; if(tmp > dp[i][i+k]) dp[i][i+k] = tmp; } } } int ret = 0; for(i = 0; i < n; i++) ret = max(ret, dp[i][i+n-1]); printf("%d
",ret); } return 0; }