Discussion :
From CP3
Given a list of coordinates of n vertices on 2D Euclidean space that are already sorted by x-coordinates (and
if tie, by y-coordinates), find a tour that starts from the leftmost vertex, then goes strictly
from left to right, and then upon reaching the rightmost vertex, the tour goes strictly from
right to left back to the starting vertex. This tour behavior is called ‘bitonic’
Although a Bitonic TSP tour of a set of n vertices is usually longer than the standard
TSP tour, this bitonic constraint allows us to compute a ‘good enough tour’ in O(n 2 ) time
using Dynamic Programming—as shown below—compared with the O(2^n × n^2 ) time for the
standard TSP tour
The main observation needed to derive the DP solution is the fact that we can (and have
to) split the tour into two paths: Left-to-Right (LR) and Right-to-Left (RL) paths. Both
paths include vertex 0 (the leftmost vertex) and vertex n-1 (the rightmost vertex). The LR
path starts from vertex 0 and ends at vertex n-1. The RL path starts from vertex n-1 and
ends at vertex 0.
Remember that all vertices have been sorted by x-coordinates (and if tie, by y-coordinates).
We can then consider the vertices one by one. Both LR and RL paths start from vertex
0. Let v be the next vertex to be considered. For each vertex v ∈ [1 . . . n − 2], we decide
whether to add vertex v as the next point of the LR path (to extend the LR path further to
the right) or as the previous point the returning RL path (the RL path now starts at v and
goes back to vertex 0). For this, we need to keep track of two more parameters: p1 and p2.
Let p1/p2 be the current ending/starting vertex of the LR/RL path, respectively.
The base case is when vertex v = n − 1 where we just need to connect the two LR and
RL paths with vertex n − 1.
double dp1(int v, int p1, int p2) {
if (v == n-1) return d[p1][v] + d[v][p2];
if (memo3d[v][p1][p2] > -0.5) return memo3d[v][p1][p2];
return memo3d[v][p1][p2] = min(
d[p1][v] + dp1(v+1, v, p2),
d[v][p2] + dp1(v+1, p1, v));
}
However, the time complexity of dp1 with three parameters: (v, p1, p2) is O(n 3 ). This is
not efficient, as parameter v can be dropped and recovered from 1+max(p1, p2) . The improved DP solution is shown below and runs in O(n 2 ).
So complete Solution:
/*
*************************
Id : Matrix.code
Task:
Date:
**************************
*/
#include <bits/stdc++.h>
using namespace std;
/*------- Constants---- */
#define LL long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<11)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<LL> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}template <class T> inline T bigmod(T p,T e,T M){LL ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return (T)ret;}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}
void IN(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);}
/*************************** END OF TEMPLATE ****************************/
const int N = 105;
int n;
double dp[N][N];
int p[N][2];
double d[N][N];
bool vis[N][N];
double calc(int p1,int p2)
{
int v= max(p1,p2)+1;
if(v==n-1){
return d[p1][v] + d[p2][v];
}
if(vis[p1][p2]) return dp[p1][p2];
double r= INF;
dp[p1][p2] = min( d[p1][v] + calc(v,p2) , d[p2][v] + calc(p1,v));
vis[p1][p2] = 1;
return dp[p1][p2];
}
int main()
{
while(scanf("%d",&n)==1) {
for(int i=0;i<n;i++) {
Sii(p[i][0],p[i][1]);
}
forn(i,n)forn(j,n){
d[i][j] = sqrt((p[i][0]- p[j][0]) * (p[i][0] - p[j][0]) + (p[i][1]-p[j][1])*(p[i][1]-p[j][1]));
}
ms(vis,0);
printf("%.2lf\n", calc(0,0));
}
return 0;
}
Furthur solving:
islands
Code for Fun 