Beyond the Void
BYVoid
POI 1997 最优旅行计划 Cheap travels

我是我做得POI的第一道题,应该也是最简单的一道题了。简单的动态规划问题,两问是类似的,仅仅优先选择的条件不同。

我仅说下第一问,状态设定 F[i]到地i个旅店时住宿的最小费用 G[i]到地i个旅店时住宿的最小过夜次数

状态转移方程 F[i]=Min{ F[j] | S[i]-S[j]<=800 } + Cost[i] G[i]=Min{ G[j] | { F[j] | S[i]-S[j]<=800 }} + 1

边界条件 F[0]=G[0]=0

目标解 F[N+1] G[N+1]

#include <iostream>

const int MAX=1002;
const int DIST=800;
const int INF=0x7FFFFFFF;

using namespace std;

int N,T,A;
int S[MAX],F[MAX],G[MAX],C[MAX],H[MAX],Ans[MAX];

void init()
{
	int i;
	freopen("tan.in","r",stdin);
	freopen("tan.out","w",stdout);
	scanf("%d%d",&T,&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d%d",&S[i],&C[i]);
	}
	S[0]=C[0]=C[N+1]=0;
	S[N+1]=T;
}

void dynamic1()
{
	int i,j;
	F[0]=G[0]=0;
	for (i=1;i<=N+1;i++)
	{
		F[i]=G[i]=INF;
		H[i]=0;
	}
	for (i=1;i<=N+1;i++)
	{
		for (j=i-1;j>=0 && S[i]-S[j]<=DIST;j--)
		{
			if (F[j]+C[i]<F[i])
			{
				F[i]=F[j]+C[i];
				G[i]=G[j]+1;
				H[i]=j;
			}
			else if (F[j]+C[i]==F[i] && G[j]+1<G[i])
			{
				G[i]=G[j]+1;
				H[i]=j;
			}
		}
	}
	A=0;
	for (i=N+1;H[i];i=H[i])
	{
		Ans[++A]=H[i];
	}
	for (i=A;i>=2;i--)
	{
		printf("%d ",S[Ans[i]]);
	}
	printf("%dn",S[Ans[1]]);
}

void dynamic2()
{
	int i,j;
	F[0]=G[0]=0;
	for (i=1;i<=N+1;i++)
	{
		F[i]=G[i]=INF;
		H[i]=0;
	}
	for (i=1;i<=N+1;i++)
	{
		for (j=i-1;j>=0 && S[i]-S[j]<=DIST;j--)
		{
			if (G[j]+1<G[i])
			{
				F[i]=F[j]+C[i];
				G[i]=G[j]+1;
				H[i]=j;

			}
			else if (G[j]+1==G[i] && F[j]+C[i]<F[i])
			{
				F[i]=F[j]+C[i];
				H[i]=j;
			}
		}
	}
	A=0;
	for (i=N+1;H[i];i=H[i])
	{
		Ans[++A]=H[i];
	}
	for (i=A;i>=2;i--)
	{
		printf("%d ",S[Ans[i]]);
	}
	printf("%d",S[Ans[1]]);
}

int main()
{
	init();
	dynamic1();
	dynamic2();
	return 0;
}
最优旅行计划
某教练想做一次旅行,将走高速公路,因为在路旁有一些价格实惠的旅馆,这样能沿途花费尽可能的少,不考虑开始点和到达点。为了安全起见,他每天只在白天行走,晚上在旅馆住宿,并且一天的路程不超过800公里。旅行社根据调查,给出了沿路旅馆的相关信息,包括每个旅馆离出发点的距离和该旅馆的价格,当然,为了整个旅行的顺利完成,任意两个旅馆之间的距离都将在800公里以内。 
你的任务是编写一个程序,在旅行距离内,对给定的输入数据,求出,
1)1)费用最少的旅行计划(即中途住宿的费用之和),如果有多个最小费用计划,则取日程最短的计划。
2)2)日程最短的旅行计划(中途在旅馆住宿的天数),如果有多个最短日程计划,则取费用最少的计划。
输入
在文本文件TAN.IN 中的第一行有用一个空格分隔的两个正整数,第一个整数d 表示旅行的距离(单位:公里)。第二个整数 h表示沿途旅社的数目, d <= 16000, h <= 1000。接下来的h行,每行有两个用单个空格分隔的正整数,说明某旅社的相关信息,第一个正整数表示离起点的距离(单位:公里),第二个正整数表示该旅社的价格。价格不会超过1000。 
输出
在文本文件TAN.OUT的第一行输出费用最少的旅行计划;第二行输出日程最短的旅行计划;旅行计划由在所有住宿的旅社组成,对每个旅社,只输出离出发点的距离即可,相邻两个数之间用一个空格分隔。
输入示例
2000 7
100 54
120 70
400 17
700 38
1000 25
1200 18
1440 40
输出示例
400 1200
400 1200

上次修改时间 2017-02-03

相关日志