Tour UVA - 1347 더 블 유클리드 여행사 문제 (dp)

1550 단어 동적 계획
사고방식 은 자서 의 알고리즘 사고방식 에 따라 두 사람 이 동시에 1 시 에서 출발 하여 서로 다른 길 을 걸 어서 n 시 에 도착 하 는 것 을 고려한다.한 사람 이 n - 1 시 에 도 착 했 을 때 마지막 에 가 야 할 경 로 는 분명 하 다. x 축 에 따라 순 서 를 정 했 기 때문에 가 야 할 가장 작은 경 로 는 반드시 dist (n - 1, n) + dist (j, n) 이다. j 는 첫 번 째 사람 이 n - 1 에 도 착 했 을 때 두 번 째 사람 이 j 시 에 도 착 했 을 때 그 경계 조건 이 확정 되 었 다 고 말 했다.다음은 배달 을 고려 합 니 다. dp [i] [j] 는 첫 번 째 사람 이 i 시 에 있 고 두 번 째 사람 이 j 시 에 있 을 때 가장 작은 길 을 가 야 한 다 는 뜻 입 니 다.그러면 dp [i] [j] = min (dp [i + 1] [j] + dist (i, i + 1), dp [i + 1] [i] + dist (i + 1, j) 는 i + 1 시 에 도착 하면 두 가지 방법 이 있 음 을 나타 낸다. i 시 에 i + 1 에 도착 하거나 j 시 에 i + 1 에 도착 할 수 있다.
#include 
using namespace std;
typedef long long ll;
const int maxn=1e5+9;
int n;
double dp[1005][1005];
struct Point
{
    double x,y;
}p[maxn];
double dist(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
} 
int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,127,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        for(int j=1;j=1;i--)
        {
            for(int j=i-1;j>=1;j--)
            {
                dp[i][j]=dp[j][i]=min(dp[i+1][j]+dist(p[i+1],p[i]),dp[i+1][i]+dist(p[j],p[i+1]));
            }
        }
        printf("%.2lf
",dp[1][2]+dist(p[1],p[2]));
    }
    return 0;
}
음성 방송 모듈 JQ8400-FL 사용
알고리즘 학습 - leetcode 659. 분할 배열 은 연속 서브 시퀀스 입 니 다.

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage