1 条题解

  • 0
    @ 2023-8-20 0:06:10
    #include <iostream>  
    #include <cstring>  
    #include <cstdio>  
    #include <cmath>  
    #include <algorithm>  
    using namespace std;  
      
    #define MAX 0x3f3f3f3f  
      
    struct Node
    {  
        double x, y;  
    };  
      
    double dp[810][810][2];  
    Node node[810];  
    int N;  
      
    double calc_dis( int i, int j )
    {  
        return sqrt( ( node[i].x - node[j].x ) * ( node[i].x - node[j].x ) + ( node[i].y - node[j].y ) * ( node[i].y - node[j].y ) );  
    }  
      
    int main()
    {  
        while( scanf( "%d", &N ) != EOF )
        {  
            for( int i = 0; i < N; i++ )
            {  
                scanf( "%lf%lf", &node[i].x, &node[i].y );  
            }  
            for( int i = 0; i < N; i++ )
            {  
                dp[i][0][0] = dp[i][0][1] = 0;  
            }  
            for( int j = 1; j < N; j++ )
            {//注意顺序首先是长度  
                for( int i = 0; i < N; i++ )
                {  
                    dp[i][j][0] = min( dp[(i+1)%N][j-1][1] + calc_dis( i, ( i + j ) % N ), dp[(i+1)%N][j-1][0] + calc_dis( i, ( i + 1 ) % N ) );  
                    dp[i][j][1] = min( dp[i][j-1][1] + calc_dis( ( i + j - 1 ) % N, ( i + j ) % N ), dp[i][j-1][0] + calc_dis( i, ( i + j ) % N ) );  
                }  
            }  
            double ans = 100000000000;  
            for( int i = 0; i < N; i++ )
            {  
                ans = min( ans, dp[i][N-1][0] );  
                ans = min( ans, dp[i][N-1][1] );  
            }  
            printf( "%.3lf", ans );  
        }  
        return 0;  
    }
    

    信息

    ID
    126
    时间
    1000ms
    内存
    256MiB
    难度
    7.9
    标签
    递交数
    1
    已通过
    1
    上传者