动态规划

“科大讯飞杯”C题总结

张老师的旅行

链接:https://ac.nowcoder.com/acm/contest/5477/C
来源:牛客网

题目描述

张老师到了一个王国去旅游,王国有n个景点,张老师到达这个城市所在的车站恰好位于第x个景点,这个王国非常特别,恰好所有著名的景点都在分布在直线上,每个景点在坐标pi上(单位:公里),张老师身体非常好,每走一公里花费一分钟。每个景点都有一个打卡点,并且必须在不迟于相应的时间(时间从张老师到达王国开始计算)前到达才能打卡成功并且给以一个打卡标记,集齐所这些标记就能获得一个大礼包。由于张老师非常想要大礼包,并且因为张老师还着急去下一个王国旅游,所以张老师希望用的时间尽量少,你能帮帮张老师吗?

输入描述:

输入的第一行,包含一个整数n(1≤n≤1000)。
第二行包含n个整数pi(1≤pi≤100000),第i个整数pi为第i个景点的坐标(坐标从小到大排列)。
最后一行包含n个整数ti(0≤ti≤10,000,000),ti表示第i个景点最迟到达的时间,时间为0则表示张老师所在车站的位置且只有一个为0。

输出描述:

输出所需的最少时间,若无解输出-1。

输入

4
1 2 3 4
0 1 2 3

输出

3

AC代码

用动态规划,dp[i][j][0/1],其中i为起点左边第i个的景点,j为起点右边第j个的景点,dp[i][j]是张老师走完左边i个和右边j个所花费的时间。所以要对所有景点分为左右两组,并且由于所有景点在一条直线上,访问远处的景点必会经过近处的景点,所以要按照距离起点的距离排序。本题输入已经按照绝对距离大小给出了,所以对输入稍微处理一下就行。

wechat picture 6 e1589353161808

dp数组的第三个维度表示落脚点,取值为0或1,0表示落脚点在起点第i个景点,1表示落脚点在起点右边第j个景点。例如dp[i][j][0]指这一步是走到左边第i个景点,dp[i][j][1]指这一步走到右边第j个景点。那么对于dp[i][j][0]来说,上一步张老师必然在左边第i-1个景点,或者右边第j个景点。dp[i][j][0]表达式(dp[i][j][1]同理)为

dp[i][j][0]=min(dp[i-1][j][0]+left[i].pos-left[i-1].pos,dp[i-1][j][1]+right[j].pos+left[i].pos);
dp[i][j][1]=min(dp[i][j-1][0]+left[i].pos+right[j].pos,dp[i][j-1][1]+right[j].pos-right[j-1].pos);

之后就是限定条件:到达每个经典不得超过最迟时间。那就是第三维下标为0的,必须小于i的时间,下标为1的必须小于j的时间。如果对于任意一个dp[i][j],无论落脚点在左边还是右边,都不符合时间限制,那么说明张老师不可能在规定时间内访问到从左边第i个到右边第j个,此时输出无解。如果只有一个情况不可能,就将其设置为无限大,以限定以后的情况。

#include<stdio.h>
#include<string.h>
using namespace std;
struct place
{
	int time;//时间 
	int pos;//位置 
}scene[1001],left[1001],right[1001];
const int inf = 0x3f3f3f3f;
int begin,leftn=0,rightn=0,n;
int dp[1001][1001][2];
int min(int x,int y)
{
	return (x>y?y:x);
}
int main()
{
	memset(dp,inf,sizeof(dp));
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		scanf("%d",&scene[i].pos);	
	}
	for (int i=0;i<n;i++)
	{
		scanf("%d",&scene[i].time);
		if (scene[i].time==0)
		{
			begin=i;//记录起点 
		}
	}
	//生成位于起点左边和右边的景点距离和时间 
	for (int i=begin-1;i>=0;i--)
	{
		leftn++;
		left[leftn].time=scene[i].time;
		left[leftn].pos=scene[begin].pos-scene[i].pos;
	}
	
	for (int i=begin+1;i<n;i++)
	{
		rightn++;
		right[rightn].time=scene[i].time;
		right[rightn].pos=scene[i].pos-scene[begin].pos;
	}
	dp[0][0][0]=0;dp[0][0][1]=0;
	for (int i=0;i<=leftn;i++)
	{
		for (int j=0;j<=rightn;j++)
		{
			if (i)	dp[i][j][0]=min(dp[i-1][j][0]+left[i].pos-left[i-1].pos,dp[i-1][j][1]+right[j].pos+left[i].pos);
			if (j)	dp[i][j][1]=min(dp[i][j-1][0]+left[i].pos+right[j].pos,dp[i][j-1][1]+right[j].pos-right[j-1].pos);
			if (dp[i][j][0]>left[i].time&&dp[i][j][1]>right[j].time)
			{
				printf("-1\n");
				return 0;
			}
			if (dp[i][j][0]>left[i].time)	dp[i][j][0]=inf;
			if (dp[i][j][1]>right[j].time)	dp[i][j][1]=inf;
		}
	}
	printf("%d\n",min(dp[leftn][rightn][0],dp[leftn][rightn][1]));
	return 0;
 } 

反思

这一题我看到数据范围就知道不能暴力搜了,但是又苦于想不出动规的解法,于是索性就先暴力搜看看,找找思路。显然是过不掉的,但是剪完枝之后的通过率(33.3%)比剪枝前(50%)还低是我没想到的。

对于这个题目,数据范围已经决定了暴力搜是做不了的。而我因为掌握的动规模型少之又少,并且这一题的限界条件在我看来不是很好处理,于是很尴尬地僵住了。

动态规划这种东西,就是你想到了就简单,想不到就完了。我决定以这道题为起点,开始去多接触些动态规划的题目。

发表评论