[jzoj 3510] [NOIP2013 시뮬레이션 11.5B팀] 최단 경로 {동적 기획}
3938 단어 동적 계획 (/ 선형 DP)
Description 평면에 n개의 점을 주고 가로 좌표의 가장 작은 점은 A이고 가장 큰 점은 B이다. 현재 Zxd는 점마다 한 번(A점 두 번)을 지나는 상황에서 A에서 B로 가고 다시 A의 가장 짧은 경로로 돌아가는 것을 알고 싶어 한다.그러나 그는 강박증 환자로 이상한 요구와 제한 조건이 많다.A에서 B로 이동할 때는 가로 좌표가 작은 점에서 큰 점까지만 이동할 수 있습니다.2. B에서 A로 돌아갈 때 가로 좌표가 큰 점에서 작은 점까지만 갈 수 있다.3. 두 개의 특수점이 있다. b1과 b2, b1은 0에서 n-1까지, b2는 n-1에서 0까지이다.당신이 그를 도와 이 문제를 해결하고 치료를 도와주세요!
Input 첫 번째 행의 세 정수 n,b1,b2,(0
Output은 한 줄로 가장 짧은 경로 길이를 출력합니다(소수점 뒤의 두 자리까지 정확함).
문제풀이의 방향
시합할 때 최단거리(spfa)를 뛰고 싶었지만 제한이 너무 많아 정해가 아니었다.정해는 동태적인 기획이다.
인용:
(dis[i][j] d i s[i] [j]는 점 i에서 점 j 사이의 직선 거리를 나타낸다) 문제를 간략하게 보면 문제는 바로 다음과 같은 문제로 볼 수 있다. 평면에 n개의 점, 각 점을 연결하는 가장 짧은 폐합 여정을 확정한다. 이런 여정은 바로 가장 왼쪽에서 시작하여 왼쪽에서 오른쪽까지 엄격하게 오른쪽, 그리고 오른쪽에서 왼쪽에서 출발점까지 엄격하게 한다.그리고 문제에서 n에서 1까지의 노선을 1에서 n까지의 노선으로 간주해도 무방하다. 그러면 우리는 1에서 n까지의 노선 두 개를 가지게 된다.f[i][j]f[i][j]를 정의하면 점 i에서 점 j까지의 경로를 나타낸다. 점 i에서 시작하여 오른쪽에서 왼쪽으로 점 1까지 한 다음에 왼쪽에서 오른쪽으로 점 j까지 이해한다.이 경로에서 점 1에서 점 max(i, j)m a x(i, j) 사이의 모든 점을 통과하고 한 번만 통과합니다.상태 이동 방정식을 열거할 수 있습니다: k를 max(i, j)+1으로 정의합니다.m a x ( i , j ) + 1 ; f[1][1]=0; f [ 1 ] [ 1 ] = 0 ; f[i][k]=min(f[i][k],f[i][j]+dis[j][k]); f [ i ] [ k ] = m i n ( f [ i ] [ k ] , f [ i ] [ j ] + d i s [ j ] [ k ] ) ; f[k][j]=min(f[k][j],f[i][j]+dis[i][k]); f [ k ] [ j ] = m i n ( f [ k ] [ j ] , f [ i ] [ j ] + d i s [ i ] [ k ] ) ; 점 b1, b2 등 특수한 상황도 고려해야 한다.그리고 k=max(i,j)+1;(i==n||j==n) k = m a x ( i , j ) + 1 ; (i==n | | j==n)의 경우.
코드
#include
#include좋은 웹페이지 즐겨찾기
