【蓝桥杯冲冲冲】动态规划初步[USACO2006 OPEN] 县集市

蓝桥杯备赛 | 洛谷做题打卡day13

• [USACO2006 OPEN] 县集市 The County Fair

  题目描述

  每年，FJ 都喜欢去参加县集市，集市上有 $n$ 个展位，每个摊位 $i$ 都会在当天的特定时间 $p_i$ 发放精美的礼品。FJ 已经听说了这一点，他希望能收集尽可能多的礼品和他的奶牛们一起分享。要想获得摊位 $i$ 发放的礼品，FJ 必须确保时间点 $p_i$ 时位于摊位 $i$。

  为了获得尽可能多的礼品，FJ 进行了一番详细的调查，通过调查FJ确定了从摊位 $i$ 到摊位 $j$ 所花费的时间 $t_{i,j}$。集市的布局很不寻常，这会导致，FJ如果在从 $i$ 到 $j$ 的过程中选择从其他摊位绕行，可能会比直接从 $i$ 到 $j$ 所花费的时间更少，然而我们耿直的 FJ 从来不这么做，如果他想从摊位 $i$ 到摊位 $j$，他一定会花 $t_{i,j}$ 的时间从 $i$ 走到 $j$。另外由于集市所在地崎岖不平，所以 $t_{i,j}$ 可能与 $t_{j,i}$ 不相同。

  FJ 在时间 $0$ 时，位于 $1$ 号摊位，请计算他最多可以收集多少奖品。

  输入格式

  第 $1$ 行：一个整数 $n$，表示摊位的数量。

  第 $2$ 行：共 $n$ 个整数，其中第 $i+1$ 的正数 $p_i$ 表示摊位 $i$ 发放礼品的时间。

  第 $n+2$ 到第 $n^2+n+1$ 行：共 $n^2$ 行，第一个 $n$ 行描述了 FJ 从摊位 $1$ 走到到摊位 $1$…$n$ 所需时间（$t_{1,1},t_{1,2},...t_{1,n}$），接下来的 $n$ 行描述了 FJ 从摊位 $2$ 走到摊位 $1$…$n$ 所需时间（$t_{2,1},t_{2,2},...t_{2,n}$），以此类推，最后的 $n$ 行描述了 FJ 从摊位 $n$ 走到摊位 $1$…$n$ 所需要的时间 $t_{n,1},t_{n,2},...t_{n,n}$。对于任意摊位 $i$，$t_{i,i}=0$。

  输出格式

  一行：一个整数，表示 FJ 最多可以领取到的奖品数量。

  样例 #1

  样例输入 #1

  4
  13
  9
  19
  3
  0
  10
  20
  3
  4
  0
  11
  2
  1
  15
  0
  12
  5
  5
  13
  0
  

  样例输出 #1

  3
  

  提示

  样例说明

  样例中集市上共有 $4$ 个摊位。$1$ 号摊位在时间 $13$ 发放礼品，$2$ 号摊位在时间 $9$ 发放礼品，$3$ 号摊位在时间 $19$ 发放礼品，$4$ 号摊位在时间 $3$ 发放礼品。

  FJ 首先从 $1$ 号摊位走到 $4$ 号摊位，用时 $3$，并在时间 $3$ 到达，正好可以领取到奖品，接着他从摊位 $4$ 走到摊位 $2$ ，用时 $5$，并在时间 $8$ 到达，在等待 $1$ 个时间点后可以领取 $2$ 号摊位的礼品，接着他从 $2$ 号摊位走到 $1$ 号摊位，用时 $4$，并在时间 $13$ 到达，从而可以收集到第 $3$ 个礼品。

  数据规模与约定

  对于 $100\%$ 的数据，$1\le n\le 400$，$0\le p_i\le 10^9$，$1\le t_{i,j}\le 10^6$。

---

思路：

这道题目我们可以用动态规划做。我们先对时间顺序排序，时间小的在前面，因为只有先经过小的时间才可以推算大的时间。接着我们就有了一个数组，用来记录在前 *i* 个礼物中最多能拿几个礼物，且第 *i* 个礼物一定要取。当然这个要经过前面的推算才能得出。

方程：

我们需要通过前面的时间推算那么我们就可以做一个判断：如果前面那个礼物发放的时间加上那个集市到这个集市的时间小于等于这个礼物发放的时间，那么就可以从那个集市过来，之所以是要一定小于等于，是因为这个礼物必须要取。通过所有可以到达的集市，更新数组的最大值。

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include <bits/stdc++.h>
using namespace std;
struct o//每一个集市的信息，下面的t和b分别是发放礼物的时间和集市的编号，记录编号是因为下面的排序有可能打乱编号
{
	int t;
	int b;
};
int p(o o1,o o2)//定义排序的优先级，发放礼物时间前的集市在前面
{
	return o1.t<o2.t;
}
int dp[401],ans;//把它们放在外面，自动清零
int main()
{
	o s[401];//定义所有的集市
	int n,t[401][401];//集市数量和走这两个集市的路的时间
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&s[i].t);
		s[i].b=i;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&t[i][j]);
	sort(s+1,s+n+1,p);
	s[0].b=1,s[0].t=0;//赋初始值，在第0分钟，FJ在第一个集市
	for(int i=1;i<=n;i++)
		for(int j=0;j<i;j++)
			if(t[s[j].b][s[i].b]+s[j].t<=s[i].t)
				dp[i]=max(dp[j]+1,dp[i]),ans=max(ans,dp[i]);//通过方程更新最大值
	printf("%d",ans);
	return 0;
}

我的一些话

• 前几天一直在学习图论算法，今天看看动态规划算法初步吧，动态规划dp有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o′ω`o)

• 如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔

• 总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）