1 条题解
-
0
#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
- 上传者