물 문제 로 인 한 반성 - 전달 방식
나 는 오늘 막 매우 물 많은 문 제 를 풀 었 는데, 이것 은 동태 계획 이다.비록 이 문 제 는 매우 물 적 이지 만 나 는 이 문 제 를 연구 하 는 데 오 랜 시간 이 걸 렸 다. 왜냐하면 나 는 이 문제 가 '전달 방식' 을 분석 하 는 범례 가 될 수 있다 고 생각 하기 때문이다.나 는 세 가지 방법 으로 이 물 문 제 를 해결 하 였 는데, 블 로 그 를 보 는 학우 들 이 깨 우 침 을 줄 수 있 기 를 바란다.
제목 의 대의
이것 은 내 가 'CodeVS' 에서 칠 한 물 문제 로' 1048 돌 병합 '이 라 고 하 는데 전형 적 인 구간 DP 물 문제 이다.여러분 먼저 이 문 제 를 보 세 요.
제목 설명 n 더미 의 돌 이 일렬 로 배열 되 어 있 으 며, 돌 더미 마다 하나의 무게 w [i] 가 있 으 며, 매번 합병 할 때마다 인접 한 두 무더기 의 돌 을 합병 할 수 있 으 며, 한 번 에 합병 하 는 대 가 는 두 무더기 의 돌 무게 와 w [i] + w [i + 1] 이다.어떤 합병 순 서 를 배정 하면 총 합병 대 가 를 최소 화 할 수 있 는 지 물 었 다.
입력 설명 Input Description 첫 줄 의 정수 n (n < = 100)
두 번 째 줄 n 개 정수 w1, w2... wn (wi < = 100)
출력 설명 출력 설명
샘플 입력 Sample Input 4
4 1 1 4
샘플 출력 샘플 출력 18
문제 풀이 의 사고 방향.
우 리 는 f [i] [j] 로 구간 [i, j] 을 합병 하 는 데 필요 한 최소 대 가 를 표시 하고 sum (i, j) 로 폐 구간 [i, j] 의 모든 돌 이 맞 는 중량 과 함께 f [i] [j] = min {f [i] [k] + f [k + 1] [j] + sum (i, j) | k * 8712 ° [i, j - 1], i < j} (특히 f [i] [i] = 0 은 돌 한 무더기 가 합병 할 필요 가 없다 는 것 을 나타 낸다).이런 분석 은 모두 매우 쉬 운 것 이지 만 어떻게 배 송 을 구축 하 는 지 는 그리 쉽 지 않다.
sum (i, j) 은 매우 구하 기 쉽다. 이것 은 간단 한 '정적 구간 과' 이기 때문에 pre 배열 O (n) 로 접두사 와 pre [i] 는 구간 [1, i] 의 합 을 표시 할 수 있 기 때문에 sum (i, j) = pre [j] - pre [i - 1], pre [i] = pre [i - 1] + w [i] (pre [0] = 0).
어떻게 전달 을 세 웁 니까?
나 는 문제 풀이 에서 이런 문 제 를 보 았 다.
#include1][n]<"pause");
return 0;
} (솔직히 처음 이 방법 을 썼 을 때 나 도 멍 했다.β。）
우 리 는 f [i] [j] 를 계산 할 때 f [i] [k] 와 f [k + 1] [j] 의 내용 을 호출 했 습 니 다. 전달 결과 의 정확 함 을 확보 하기 위해 서 는 순환 순서 (순 추 또는 역 추) 를 설계 하여 f [i] [j] 를 계산 하기 전에 모든 접두사 와 모든 접 두 사 를 계산 해 야 합 니 다. 접 두 사 를 사용 할 수 있 도록 순 추 '오른쪽 경계' 를 사용 할 수 있 습 니 다.이렇게 하면 왼쪽 경계 가 같은 상황 에서 조건 을 만족 시 킬 수 있 습 니 다. 접 두 사 를 확보 하고 왼쪽 경 계 를 역 추진 하 는 방법 을 사용 할 수 있 습 니 다. 이렇게 하면 오른쪽 경계 가 같은 상황 에서 접 두 사 는 먼저 계산 할 수 있 습 니 다. 위조 코드 는 바로 다음 과 같 습 니 다.
For j=1 to n
For i=j-1 downto 1
f[i][j] = INF
For k=i to j-1
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum(i,j))(메모: 위의 C + 코드 에서 i 로 '오른쪽 경계' 를 표시 하고 j 는 '왼쪽 경계' 를 표시 하 며 의사 코드 와 다 릅 니 다.)
이것 은 알고리즘 사상 을 매우 시험 하 는 전달 방식 으로 학생 들 이 완전히 이해 한 후에 계속 읽 기 를 바란다.
간단 하고 거 친 방법 1: 기억 화 검색
기억 화 검색 은 전달 을 대체 하 는 좋 은 방법 이다. 기억 화 검색 에서 우 리 는 전달 방법 을 생각 하 는 데 오 랜 시간 이 걸 릴 필요 가 없다.
매우 본질 적 인 문제 로 돌 아 왔 다. 왜 우 리 는 푸 시 를 사용 해 야 합 니까? 우 리 는 푸 시 를 사용 해 야 하 는 이 유 는 재 귀 를 대체 하기 위해 서 입 니 다. 재 귀 하 는 과정 에서 같은 데 이 터 는 몇 번 도 계산 되 지 않 았 고, 푸 시 는 모든 데 이 터 를 한 번 만 계산 한 후에 저장 하 는 것 입 니 다. 다음 에 필요 할 때 직접 호출 하 는 것 입 니 다. 다시 계산 하 는 것 이 아 닙 니 다.
사실 우 리 는 다른 방법 을 이용 하여 '재 귀' 를 최적화 할 수 있 습 니 다. 재 귀 도 사용 할 수 있 고 계 산 된 데 이 터 를 기록 할 수 있다 면 정말 좋 습 니 다. 따라서 우 리 는 하나의 visit 배열 을 정의 할 수 있 습 니 다. visit [i] [j] 는 f [i] [j] 가 계산 되 었 는 지 여 부 를 표시 할 수 있 습 니 다. 우리 가 f [i] [j] 의 값 이 필요 할 때 우리 가 이전에 f [i] [j] 를 계산 한 적 이 있 는 지 판단 할 수 있 습 니 다.계산 을 해 보면 f [i] [j] 로 되 돌아 갑 니 다. 그렇지 않 으 면 visit [i] [j] 를 1 로 붙 이 고 '재 귀' 처럼 f [i] [j] 의 값 을 계산 한 다음 에 되 돌아 갑 니 다. 이러한 기억 기능 을 가 진 '재 귀' 를 '기억 화 검색' 이 라 고 합 니 다. 이런 방법 은 이 문제 에서 가장 큰 장점 은 바로 전달 과 같이 모든 f [i] [j] 를 보장 합 니 다.값 은 한 번 만 계산 되 고 시간 복잡 도와 전달 은 완전히 같다.
기억 화 검색 은 이 문제 에서 시간 적 으로 우세 한 것 은 없 지만, 일부 문제 에 서 는 전달 보다 훨씬 빠르다. 전달 은 모든 상태 에 대응 하 는 결 과 를 구 할 수 있 지만, '기억 화 검색' 은 우리 가 필요 로 하 는 상 태 를 계산 할 뿐이다.β가 지 를 치다.
위조 코드 를 보십시오:
Sovef(int i,int j)
if visit[i][j] == 0
visit[i][j] = 1
f[i][j]=INF
For k=i to j-1
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum(i,j))
return f[i][j]코드 를 보십시오:
#include1,j)+pre[j]-pre[i-1]);
}
return f[i][j];
}
int main()
{
memset(f,255,sizeof(f));
int n;cin>>n;
for(int i=1;i<=n;i++)
{
int w;cin>>w;
pre[i]=pre[i-1]+w;
}
cout<1,n)<return 0;
} '기억 화 검색' 은 '선택 공포 증' 환자 의 좋 은 선택 이 라 고 할 수 있다.
간단 하고 거 친 방법 2: 구간 길이 관계 에 따라 전달
첫 번 째 방법 은 한 구간 을 계산 할 때 모든 접두사 와 모든 접 두 사 는 이미 계산 을 거 쳤 다 는 것 을 보증 할 수 있 습 니 다. 곰 곰 이 생각해 본 후에 이렇게 문 제 를 생각 하 는 것 은 정말 딱딱 합 니 다. 왜 구간 의 길이 에 따라 순환 하 는 방법 을 고려 하지 않 습 니까? [i, j] 의 접두사 든 [i, j] 의 접두사 든 [i, j] 의 접두사 든 [i, j] 의 접두사 이기 때 문 입 니 다.그 자체 의 일부분 이기 때문에 그들의 길 이 는 반드시 [i, j] 보다짧 아야 합 니 다. 만약 우리 가 구간 의 길이 에 따라 짧 은 구간 에서 긴 구간 까지 각 구간 의 f 값 을 계산 할 수 있다 면, 먼저 모든 길이 가 2 인 구간 을 구하 고, 길이 가 3, 4, 5... 길이 가 n 인 구간 까지 구 할 수 있다 면, 이 문 제 를 완벽 하 게 해결 할 수 있 습 니 다. 각 위 치 를 시작 으로 하 는 고정 길이 의 문자열 은 나 에 게 만 계산 되 기 때 문 입 니 다.회, 그래서 시간 복잡 도 는 변 하지 않 는 다.
의사 코드 는 다음 과 같 습 니 다:
For k=2 to n
For i=1 to n-k+1
f[i][i+k-1]=INF
For j=1 to i+k-2
f[i][i+k-1]=min(f[i][i+k-1],f[i][j]+f[j+1][i+k-1]+sum(i,i+k-1))코드 는 다음 과 같 습 니 다:
#include1][n]<return 0;
} 첫 번 째 방법 에 비해 이런 방법 은 이해 하기 쉽 고 전달 사상의 표현 이기 도 하 며 이 문제 에서 저 는 학생 들 이 사용 하 는 방법 을 추천 합 니 다.
후기
위의 세 가지 문 제 를 해결 하 는 방법 을 총괄 하 는 당신 은 시사 점 을 느끼 고 있 습 니까? 한 가지 문 제 는 여러 가지 방법 으로 해결 할 수 있 습 니 다. "이것 은 자연의 이치 입 니 다." 그리고 여러 가지 방법 도 각각 우열 이 있 습 니 다. 학생 들 이 스스로 자세히 음미 하 기 를 바 랍 니 다. 가장 중요 한 것 은 코드 를 쓸 때 '거시적인' 사상 이 있어 야 하고 '소탈 한' 사상 이 있어 야 합 니 다.. 사고 가 문제 에 국한 되 지 않도록 사고방식 에 빠 져 야 더 좋 은 문 제 를 해결 할 방법 을 찾 을 수 있다.
[2017.12.24] 7 개 월 후의 오늘 에 저 는 이 문 제 는 '평행 사각형 최적화' 를 통 해 O (n2) 가 될 수 있다 는 것 을 알 게 되 었 습 니 다. 코드 는 다음 과 같 습 니 다.
#include//
for(int i=1;i+len<=n;i++){
int end=i+len,tmp=0x7f7f7f7f,k;
for(int j=p[i][end-1];j<=p[i+1][end];j++){//
if(f[i][j]+f[j+1][end]+pre[end]-pre[i-1]1][end]+pre[end]-pre[i-1];
k=j;
}
}
f[i][end]=tmp;p[i][end]=k;
}
}
printf("%d
",f[1][n]);
return 0;
} 제목:
codevs 3002 돌 병합 3
오늘 이 문 제 는 신기 한 욕심 알고리즘 도 사용 할 수 있다 고 들 었 습 니 다. 시간 복잡 도 를 O (nlogn) 로 바 꿀 수 있 습 니 다. 예 를 들 어 GarsiaWachs 알고리즘 과 원 방 욕심 등 입 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
