UVA1347 旅行 Tour 題解【dp】

原題位址(vjudge)

這題還是有點意思的，你珂以了解為要找兩條除了起點和終點之外沒有任何點是相等的路徑。這題就和某經典題不太一樣了，某經典題是可以重複的。是以用 d p [ i ] [ j ] dp[i][j] dp[i][j]表示同時走到第 i i i個點和第 j j j個點就不是很好了。那怎麼表示呢？珂以用 d p [ i ] [ j ] dp[i][j] dp[i][j]表示同時走到 i i i和 j j j且 max ⁡ ( i , j ) \max(i,j) max(i,j)全部都走過。易得 d p [ i ] [ j ] = d p [ j ] [ i ] dp[i][j]=dp[j][i] dp[i][j]=dp[j][i]，規定一下所有狀态必須 i > j i>j i>j，

狀态轉移方程：

d p [ i ] [ j ] = m i n ( d p [ i + 1 ] [ j ] + d i s [ i ] [ i + 1 ] , d p [ i + 1 ] [ i ] + d i s [ i + 1 ] [ j ] ) dp[i][j]=min(dp[i+1][j]+dis[i][i+1],dp[i+1][i]+dis[i+1][j]) dp[i][j]=min(dp[i+1][j]+dis[i][i+1],dp[i+1][i]+dis[i+1][j])

d p [ i + 1 ] [ j ] dp[i+1][j] dp[i+1][j]表示第一個人從 i → i + 1 i \to i+1 i→i+1，是以加上 d i s [ i ] [ i + 1 ] dis[i][i+1] dis[i][i+1]， d p [ i + 1 ] [ i ] dp[i+1][i] dp[i+1][i]原式等于 d p [ i ] [ i + 1 ] dp[i][i+1] dp[i][i+1]，即從 j → i + 1 j\to i+1 j→i+1（ 所 有 小 于 i 的 點 都 已 走 過 ， 所 以 隻 能 走 到 i + 1 所有小于i的點都已走過，是以隻能走到i+1 所有小于i的點都已走過，是以隻能走到i+1），隻不過要保持第一維小于第二維，是以隻能轉成 d p [ i + 1 ] [ i ] dp[i+1][i] dp[i+1][i]，加上 d i s [ i + 1 ] [ j ] dis[i+1][j] dis[i+1][j]，初始條件：

路徑預處理：

void compare(void) 
{
	memset(dp,0,sizeof(dp)) ;
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=n;j++) 
		{
			double c=sqrt(abss(x[i]-x[j])*abss(x[i]-x[j])+abss(y[i]-y[j])*abss(y[i]-y[j])); //abss指絕對值
			g[i][j]=g[j][i]=c;
		}
	}
	return ;
}
           

狀态轉移：

for(int i=n-1;i>=2;i--) 
	{
		for(int j=1;j<i;j++) 
		{
			dp[i][j]=min(dp[i+1][j]+g[i][i+1],dp[i+1][i]+g[i+1][j]);
		}
	}
           

C o d e \color{blue}Code Code：

# include <bits/stdc++.h>
using namespace std;
int n;
const int N=1010;
double x[N],y[N];
double g[N][N];
double dp[N][N];
double abss(double a) 
{
if(a>=0) return a;
return -a;
}
void compare(void) 
{
	memset(dp,0,sizeof(dp)) ;
	for(int i=1;i<=n;i++) 
	{
		for(int j=1;j<=n;j++) 
		{
			double c=sqrt(abss(x[i]-x[j])*abss(x[i]-x[j])+abss(y[i]-y[j])*abss(y[i]-y[j]));
			g[i][j]=g[j][i]=c;
		}
	}
	for(int i=1;i<=n;i++) dp[n][i]=g[n][i];
	return ;
}
void solve(void) 
{
	for(int i=n-1;i>=2;i--) 
	{
		for(int j=1;j<i;j++) 
		{
			dp[i][j]=min(dp[i+1][j]+g[i][i+1],dp[i+1][i]+g[i+1][j]);
		}
	}
	cout<<fixed<<setprecision(2)<<dp[2][1]+g[2][1]<<endl ;
}
int main(void) 
{
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;i++) 
		{
			cin >> x[i] >> y[i];
		}
		compare() ;
		solve() ;

	}
	return 0;
}
           

n i c e ! nice! nice!