동적 계획 - 구간 dp

구간 dp:
우선 예제: NOI 1995 돌 합병
제목 설명
원형 운동장 주변 에 N 더미 의 돌 을 놓 고 돌 을 차례대로 한 무더기 로 합 쳐 야 한다. 매번 인접 한 2 더 미 를 선택 하여 새로운 한 무더기 로 합 칠 수 있 도록 규정 하고, 새로운 돌의 수 를 이번 합병의 득점 으로 기록 해 야 한다.
1 개의 알고리즘 을 시험 적 으로 설계 하여 N 개의 돌 더 미 를 1 더미 로 합 친 최소 득점 과 최대 점 수 를 계산한다.
입 출력 형식
입력 형식:
데이터 의 첫 번 째 줄 시험 정수 N, 1 ≤ N ≤ 100 은 N 더미 의 돌 이 있 음 을 나타 낸다. 두 번 째 줄 은 N 개의 수가 있 는데 각각 각 더미 의 돌 수 를 나타 낸다.
출력 형식: 출력 총 2 줄, 첫 번 째 행위 최소 득점, 두 번 째 행위 최대 득점.
입력 예시:                                                출력 예시:
4                                                                 434 5 9 4                                                        54
얼핏 보면 욕심 인 줄 알 았 다.물론 욕심 이 있 지만 정 해 는 아니다.구간 dp 로 풀 려 있 습 니 다:
dpmax [i] [j] 는 구간 내 에 돌 을 합 친 것 을 나타 낸다. 최대 치, 그리고 우 리 는 매 거 할 수 있다. 정지점 k 。이 문 제 는 원형 운동장 이 라 고리 모양 에 정지점 이 매 거 져 있다.기왕 이렇게 된 이상 우 리 는 이 돌 을 분할 해 야 한다.분명히 우 리 는 이 돌의 분할 선 으로 k 를 매 거 해 야 한다.
합병 할 수 밖 에 없 으 니까. 인접 하 다 돌멩이 접두사 자, 실현: sum[i] 전에 i 돌무더기 의 수량 과.
처음부터 끝까지 합병 할 수 있 기 때문에, 우 리 는 많이 열 어야 한다. n 개 공간 도 많이 순환 해 야 한다. n 차례그리고 매 거 구간 헤드 엔 드 ，한 구간 씩 찾다 최대 치 / 최소 치 ，마지막 으로 출력 하면 됩 니 다.
그래서 우 리 는 동적 전이 방정식 을 얻 었 다.
f[i][j] = max(f[i][k] + f[k+1][j] + sum(i,j));그 중 1 < = i < = k
다음은 전달 과정 을 고려 한 것 이다.
우 리 는 매 거 k 를 통 해 i 와 j 를 구분 해 야 한다. 그러면 매 거 i 와 j 를 통 해 상 태 를 이전 하면 일부 k 값 이 필요 한 상 태 를 확정 했다 고 보장 할 수 없 음 이 분명 하 다.
하지만 이 정도 면 i 와 j 는 확실 하지 않다.그래서 우 리 는 j - i 를 매 거 하고 j - i 에서 k 를 매 거 해 야 합 니 다. - -TIMI 에서 발췌k 의 방법,
AC 코드 는 다음 과 같 습 니 다.

#include
#include
#include
#include 
using namespace std;
const int maxn=1e10;
int n,ans2,ans1,dp1[1001][1001],dp2[1001][1001],num[1001];
int s[1001];//      
inline int sum(int i,int j){return s[j]-s[i-1];}//                 
int main(){+
	cin>>n;
	for(int i=1;i<=n+n;i++){
		cin>>num[i];
		num[i+n]=num[i];
		s[i]=s[i-1]+num[i];//      Q 
	}
	for(int p=1;p