Luogu 1880 합병 돌

Luogu 1880 합병 돌 (선형 동적 계획)
전형 적 인 구간 형 동적 계획.
-- -- -- -- -- -- -- -- -- -- -- -- -- 문제:https://www.luogu.org/problem/P1880
제목 설명: 원형 운동장 주변 에 N 더미 의 돌 을 놓 고 돌 을 차례대로 한 더미 로 합 쳐 야 한다. 매번 인접 한 2 더 미 를 선택 하여 새로운 돌 로 합 칠 수 있 도록 규정 하고 새로운 돌 더 미 를 이번 합병 의 득점 으로 기록 해 야 한다.
1 개의 알고리즘 을 시험 적 으로 설계 하여 N 개의 돌 더 미 를 1 더미 로 합 친 최소 득점 과 최대 점 수 를 계산한다.
입력 형식: 데이터 의 첫 번 째 줄 시험 정수 N, 1 ≤ N ≤ 100, N 돌 더미 가 있 음 을 표시 합 니 다. 두 번 째 줄 에는 N 개의 수가 있 으 며, 각각 돌 더미 의 개 수 를 표시 합 니 다.
출력 형식: 출력 총 2 줄, 첫 번 째 행위 최소 득점, 두 번 째 행위 최대 득점.
샘플: 입력: 445 9 4 출력: 4354 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 사고방식:
1. 선행 처리 접두사 와: 선행 처 리 를 하고 그 다음 에 i - j 의 돌 과 를 사용 해 야 하기 때문에 먼저 접두사 와 a [j] - a [i - 1] 즉 i - j 의 돌 과 고리 모양 의 구조 로 인해 2 * n 까지 처리 합 니 다.
2. 최 우수 서브 구조: 최 우수 해 (최대 치 를 예 로 들 면) 를 얻 으 려 면 각 구간 의 합병 이 최 우수 해 야 한다. 한 구간 이 최대 득점 이 아니 라 고 가정 하면 이 구간 은 최대 득점 으로 바 뀌 고 최종 결 과 는 원래 의 결과 보다 더욱 좋 으 며 최 우수 서브 구 조 를 만족 시 켜 야 한다.
3. 상태: 선형 인 이상 dp [i] [j] 를 i 에서 j 로 통합 하 는 최대 득점 (최소 득점) 으로 정의 하 는 것 도 좋 습 니 다.
4. 상태 전이 방정식: 그러면 우 리 는 상태 전이 방정식 을 어떻게 얻 을 수 있 습 니까? 단점 k 를 매 거 하여 긴 구간 을 짧 은 구간 으로 바 꿀 수 있 습 니 다. 상태 전이 방정식 은 매우 뚜렷 합 니 다.
dp[i][j]=max(dp[i][k]+dp[k+1][j]+a[j]-a[i-1]）.
5. 이동 순서: 이 문제 의 상태 이동 방정식 은 매우 좋 지만 이동 순 서 는 확실히 어 려 운 점 이 있다. 만약 에 순환 하고 있다 고 가정 하면 매 거 k 를 통 해 i, j 로 나 누 면 매 거 i 와 j 를 통 해 상태 이동 을 하면 일부 k 값 이 필요 한 상 태 를 이미 확정 했다 고 보장 할 수 없다. 예 를 들 어 i: 1 to 10; j: 1 to 10; k: 1 to 9; i = 1, j = 5, k = 3 일 때 상태 f 가 분명 하 다.[k + 1] [j] 결과 가 없습니다.
그래서 우 리 는 매 거 구간 의 길이, 좌우 점 이 필요 하 다. 먼저 길 이 를 2 로 합 친 다음 에 3 to n 을 합 쳐 야 필요 한 상 태 를 확정 할 수 있다.
6. 고리 형 구 조 는 어떻게 처리 합 니까? 고리 형 구조 이기 때문에 우 리 는 뒤에서 앞의 수 를 복사 하여 돌 수 를 2 * n 으로 확장 합 니 다.
예: 우 리 는 예 를 들 어 4, 5, 9, 4 - > 4, 5, 9, 4, 5, 4, 4, 5, 9, 4, 4, 5, 9, 4, 4, 4, 5, 9, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4
7. 결과: 마지막 으로 n 구간 내 최 적 화 된 길 이 를 통계 하면 된다.
——————————————————————————————————
코드:

#include
#include
#include
#include
#include
using namespace std;
const int MAXN = 300 + 10; 
int n,ansmin,ansmax,dp1[MAXN][MAXN],dp2[MAXN][MAXN];// dp1    i--j     ， dp2    i--j      
int a[MAXN]; // a       ， a[j]-a[i-1]  i--j  。 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		a[i+n]=a[i];
		a[i]+=a[i-1]; 
	}
	for(int i=n+1;i<=2*n;i++)
	a[i]+=a[i-1]; //     ，    2*n 
	for(int p=1;p<n;p++)  //    
    {  
        for(int i=1,j=i+p;(j<n+n) && (i<n+n);i++,j=i+p)  //    
        {  
            dp2[i][j]=999999999;  
            for(int k=i;k<j;k++)   //  
            {  
                dp1[i][j] = max(dp1[i][j], dp1[i][k]+dp1[k+1][j]+a[j]-a[i-1]);   
                dp2[i][j] = min(dp2[i][j], dp2[i][k]+dp2[k+1][j]+a[j]-a[i-1]);  
                //       dp[i][j]=max(dp[i][k]+dp[k+1][j]+a[j]-a[i-1]); 
            }  
        }  
    }  
	ansmin=1e9+7;
	ansmax=0;
	for(int i=1;i<=n;i++)
	{
		ansmax=max(ansmax,dp1[i][i+n-1]);
		ansmin=min(ansmin,dp2[i][i+n-1]);
	}//       n            ，         
	cout<<ansmin<<"
"<<ansmax;
	return 0;
}

2019.10.26
By October