[동적 계획] 돌 합병 문제 (링) (ssl 1597)

돌 합병 문제 돌 합병 문제 돌 합병 문제
Description
원형 운동장 사방 에 n 더미 의 돌 이 놓 여 있다.지금 은 돌 을 차례대로 한 무더기 로 합 쳐 야 한다.매번 인접 한 돌 2 무 더 기 를 골 라 새로운 더미 로 만 들 고 새로운 돌 한 무 더 기 를 이번 합병의 득점 으로 기록 하도록 규정 하고 있다.n 개의 돌 을 한 무더기 로 합 친 최소 득점 과 최대 득점 을 계산 하 는 알고리즘 을 시험 적 으로 설계 하 다.
프로 그래 밍 작업:
주어진 n 더미 의 돌 에 대해 프로 그래 밍 계산 은 한 무더기 의 최소 득점 과 최대 득점 으로 합 쳐 진다.
Input
입력 은 여러 그룹의 테스트 데 이 터 를 포함 하고, 각 그룹의 테스트 데 이 터 는 두 줄 을 포함한다.
첫 번 째 줄 은 정수 n, 1 & lt; = n & gt; = 100 으로 n 개의 돌 이 쌓 여 있다 는 뜻 이다.
두 번 째 줄 에는 n 개의 수가 있 는데 각각 돌 더미 의 개 수 를 나타 낸다.
Output
각 그룹의 입력 데이터 에 대해 두 줄 을 출력 합 니 다.
첫 번 째 줄 의 수 는 최소 득점 이다.두 번 째 줄 의 수 는 최대 득점 이다.
Sample Input
4
4 4 5 9
Sample Output
43
54
제목 의 대의:
n 더미 의 돌 이 있 습 니 다. 하나의 고리 로 둘러싸 여 있 습 니 다. 인접 한 두 더 미 를 합 칠 수 있 습 니 다. 두 더미 의 무게 의 합 은 당신 의 점수 입 니 다. 최대 점수 와 최소 점 수 를 요구 합 니 다.
문제 풀이 방법:
먼저 돌 합병 (비 환형) 문 제 를 풀 고 이 문 제 를 푸 는 것 을 권장 합 니 다. 본 체 는 두 가지 방법 이 있 습 니 다.
방법 하나 방법 하나
우 리 는 먼저 두 번 째 배열 f [i] [j] 로 i 쌍 부터 뒤의 j 개수 의 최소 치 (최대 l) 를 표시 한 다음 에 뒤에서 복사 한 다음 에 돌 과 합병 하 는 것 과 차이 가 많 지 않다.
동적 이동 방정식:
f [ i ] [ l e n ] = m i n ( f [ i ] [ l e n ] , f [ i ] [ k ] + f [ i + k ] [ l e n − k ] + s [ i + l e n − 1 ] − s [ i − 1 ] ) f[i][len]=min(f[i][len],f[i][k]+f[i+k][len-k]+s[i+len-1]-s[i-1]) f[i][len]=min(f[i][len],f[i][k]+f[i+k][len−k]+s[i+len−1]−s[i−1])
l [ i ] [ l e n ] = m a x ( l [ i ] [ l e n ] , l [ i ] [ k ] + l [ i + k ] [ l e n − k ] + s [ i + l e n − 1 ] − s [ i − 1 ] ) l[i][len]=max(l[i][len],l[i][k]+l[i+k][len-k]+s[i+len-1]-s[i-1]) l[i][len]=max(l[i][len],l[i][k]+l[i+k][len−k]+s[i+len−1]−s[i−1])
설명:
f [i] [k] 는 앞, i + k 는 뒤의 시작, len - k 는 길이 가 len 이 k 를 사 용 했 기 때문에 k 를 빼 야 합 니 다. i + len - 1 은 이 단락 의 뒤에 있 습 니 다. i 번 째 도 요구 하기 때문에 i - 1 을 빼 야 합 니 다.

#include
#include
using namespace std;
int a[205],f[205][205],l[205][205],s[205],n,minn,maxx;
int main()
{
	memset(f,127/3,sizeof(f));
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	  {
	  	scanf("%d",&a[i]);
	  	s[i]=s[i-1]+a[i];
	  	f[i][1]=0;
	  }
	for (int i=n+1;i<=n*2;i++)
	  {
	  	s[i]=s[i-1]+a[i-n];//    
	  	f[i][1]=0;
	  }
	for (int len=2;len<=n;len++)//  
	  for (int i=1;i<=n*2-len;i++)//    ，n-len+1+n-1=n*2-len
	    for (int k=1;k<len;k++)//   
		  {
		    f[i][len]=min(f[i][len],f[i][k]+f[i+k][len-k]+s[i+len-1]-s[i-1]);//    
			l[i][len]=max(l[i][len],l[i][k]+l[i+k][len-k]+s[i+len-1]-s[i-1]);//    
		  }
	minn=2147483647;
	for (int i=1;i<=n;i++)
	  {
	  	minn=min(minn,f[i][n]);//   
	  	maxx=max(maxx,l[i][n]);//   
	  }
	printf("%d
%d",minn,maxx);
}

방법 2 방법 2 방법 2
우 리 는 뒤에 한 단락 (f 와 l 이 표시 한 것 과 같다) 을 추가 하지 않 고, 직접 mod 의 방법 으로 당신 의 직접 을 초과 하여 1 부터 뒤로, 본 방법 은 동적 이동 방정식 을 상세 하 게 본다.
동적 전이 방정식
f [ i ] [ l e n ] = m i n ( f [ i ] [ l e n ] , f [ i ] [ k ] + f [ ( i + k − 1 ) m o d n + 1 ] [ l e n − k ] + f j ( i , i + l e n − 1 ) ) ; f[i][len]=min(f[i][len],f[i][k]+f[(i+k-1)modn+1][len-k]+fj(i,i+len-1)); f[i][len]=min(f[i][len],f[i][k]+f[(i+k−1)modn+1][len−k]+fj(i,i+len−1));
l [ i ] [ l e n ] = m a x ( l [ i ] [ l e n ] , l [ i ] [ k ] + l [ ( i + k − 1 ) m o d n + 1 ] [ l e n − k ] + f j ( i , i + l e n − 1 ) ) ; l[i][len]=max(l[i][len],l[i][k]+l[(i+k-1)modn+1][len-k]+fj(i,i+len-1)); l[i][len]=max(l[i][len],l[i][k]+l[(i+k−1)modn+1][len−k]+fj(i,i+len−1));
설명:
(i + k - 1) mod n + 1 은 왜 (i + k) mod n 으로 쓰 지 않 습 니까?i + k = n 일 때 결 과 는 0, 0 이 우리 의 계산 범위 에 있 지 않 기 때문에 우 리 는 (i + k - 1) mod n + 1 을 사용 해 야 한다. 이런 말 을 사용 하면 i + k = n 일 때 결 과 는 n 이다.fj (i, i + len - 1) 는 i 에서 i + len - 1 사이 의 수 를 계산한다.

#include
#include
using namespace std;
int a[105],f[105][105],l[105][105],s[105],n,minn,maxx;
int fj(int x,int y)
{
	if (y<=n) return s[y]-s[x-1];//    n
	return fj(x,n)+fj(1,y-n);//   
}
int main()
{
	memset(f,127/3,sizeof(f));
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	  {
	  	scanf("%d",&a[i]);
	  	s[i]=s[i-1]+a[i];
	  	f[i][1]=0;
	  }
	for (int len=2;len<=n;len++)//  
	  for (int i=1;i<=n;i++)//   
	    for (int k=1;k<len;k++)//   
		  {
		    f[i][len]=min(f[i][len],f[i][k]+f[(i+k-1)%n+1][len-k]+fj(i,i+len-1));//      
			l[i][len]=max(l[i][len],l[i][k]+l[(i+k-1)%n+1][len-k]+fj(i,i+len-1));//      
		  }
	minn=2147483647;
	for (int i=1;i<=n;i++)
	  {
	  	minn=min(minn,f[i][n]);//    
	  	maxx=max(maxx,l[i][n]);//    
	  }
	printf("%d
%d",minn,maxx);
}