12.19 单源最短路(dij,dp),最快逃跑方式(贪心模拟)

2023-12-19 22:19:23

P1359 租用游艇

就是说第一行为1到2~n,第二行为2到3~N.最终构建出来的是一个无向图,

然后源点是1,目标点是n,问从1到n的最短路

dp

#include<iostream>
#include<queue>
using namespace std;
int dp[201];//表示从i号到n所需的最少成本
int n;
int arr[201][201];
int main() {
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {//i表示起点
		for (int j = i + 1; j <= n; j++) {//j表示终点
			cin >> arr[i][j];
		}
		dp[i] = 1e9;
	}

	for (int i = n - 1; i >= 1; i--) {//i表示初始状态
		for (int j = i + 1; j <= n; j++) {//j表示终点
			dp[i] = min(dp[i], arr[i][j] + dp[j]);//表示划分子问题,要向到n位,就要到j位,要到J位,就要到i位,从i位到j位需要arr[i][j]的代价
		}//min的后项表示状态转移,从i转移到j
	}
	cout << dp[1];
	return 0;
}

从高处往低处更新,这样可以保证在低处调用高处的dp时,是唯一确定的,就是不会再被更新的大小

如果从低处往高处更新,就是类似于dij的思路,但又不完全是?

最短路

dij的想法就是每次迭代,找到一个未访问过的,距离最近的点,找到后,就依据这个点去更新dis数组。dis数组记录的是固定起点到不同终点的最短距离,其下标就代表着终点的编号。

也是划分的一个思想,就是找到一个新点后,看通过新点到目标点的代价小,还是原来的代价小

即dis[j]=min(dis[j],dis[u]+g[u][j])

dis[u]表示先到u点,g[u][j]表示通过u点再到j点

#include<iostream>
#include<queue>
using namespace std;
int g[201][201];
int n;
int dis[201];
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {//i表示起点
		for (int j = 1; j <= n; j++) {//j表示终点
			g[i][j] = 9999999;
			if (i == j)g[i][j] = 0;
		}
	}
	for (int i = 1; i <= n - 1; i++) {
		for (int j = i + 1; j <= n; j++) {
			cin >> g[i][j];
		}
	}
	for (int i = 2; i <= n; i++) {
		dis[i] = g[1][i];
	}
	dis[1] = 0;
	bool vis[201];
	memset(vis, 0, sizeof(vis));
	vis[1] = 1;
	for (int i = 1; i <= n - 1; i++) {//这个含义只表示迭代次数
		int mind = 99999999, u ;//注意已被访问的dis不可能再被更新,因为其是在可达的最小基础上直接到达的,而其他的方式,即使后续的代价很小,但因为第一步的代价就已经不如了,所以也不可能再被更新,就是类似于三角形任意两边和大于第三边,即使两边中有一边很短
		//但需注意,可以确定的是最小的未访问的dis元素,而不是任意的未访问的dis元素,每次的最小dis元素都不可能再被更新了
		for (int j = 2; j <= n;j++) {//每次都从此时dis数组里最小的点出发,这个循环的目的是为了找到此时dis数组里未被访问的最小的元素
			if (!vis[j]&&dis[j]<mind) {
				mind = dis[j];
				u = j;
			}
		}
		//由于每次都会访问掉一个点,所以每次可供选择的点越来越少,即每次迭代都会确定一个最终的点
		//不可能有更短的距离到这个点了,除非有负权,即一开始到u点的代价可能比较大,但是u到v有一个负权,使其可以完全弥补掉一开始很大的代价
		//如果没有负权,那么此时直接在可达的所有路径中找,第一次找到的所有路里最小的就是最后的结果,通过其他路再到同样的基于该最小路到的点,一定没有通过此时最小路到的代价小
		//因为没有负权,那么后续的所有路径都是建立在开始的一个很大的代价基础上,且没有负权可以减小这个代价
		vis[u] = 1;
		for (int j = 2; j <= n; j++) {
			dis[j] = min(dis[j], dis[u] + g[u][j]);//在此时已确定的新节点基础上向外延申
		}
	}
	cout << dis[n];
	return 0;
}

小优化?

dij得到的是单源点到各个点的最短距离,但如果只关心某一个点的最短距离,那么在迭代中得到u=n时就可以直接退出

	//dij算法得到的是源点到所有点的最短路径
	for (int i = 1; i <= n - 1; i++) {//每次确定一个dis,那么共需要迭代N-1轮
		int mind = 1e9, u;
		for (int j = 2; j <= n; j++) {//由于是到所有点的最短路径,所以除了自身以外,其他所有点都要不断去尝试更新
			//如果说是特指n的话,那么在这里取出的是n时,就意味着后续都不可能再更新出更低的成本了
			if (!vis[j] && dis[j] < mind) {
				mind = dis[j];
				u = j;
			}
		}
		vis[u] = 1;
		if (u == n)break;
		for (int j = 2; j <= n; j++) {
			dis[j] = min(dis[j], dis[u] + g[u][j]);//原策略,或者先到U,再通过u到j
			//注意这一步是依据新点u来更新各个dis元素
		}
	}

BOOL类型要初始化

在C++中,bool类型的数组未初始化时,其元素的值是不确定的,可能是true,也可能是false。因此,使用未初始化的bool数组时需要谨慎,最好先对其进行初始化操作,以确保其元素的值是可预测的。

少了memset就会报错

memset就是初始化,用for也行

它的头文件是string.h

P1095 [NOIP2007 普及组] 守望者的逃离

贪心的话,优先就是用魔法,直到距离很短

DP

dp[t][m]表示剩余时间为t,魔力剩余为m时所能走的最远距离

dp[t][m]=max(dp[t-1][m+4],dp[t-1][m]+17,dp[t-1][m-10]+60);

//这么一看有点像BFS

贪心,模拟(模拟为主)

int m, s, t;
	cin >> m >> s >> t;
	int s1 = 0, s2 = 0;
	//s1就是优先跑步,s1存为最优策略
	for (int i = 1; i <= t; i++) {
		s1 += 17;
		if (m >= 10) {
			s2 += 60;
			m -= 10;
		}//s2只能一直闪现,因为闪现的总体收益是更高的
		else {
			m += 4;
		}
		if (s2 > s1) {//如果闪现在某个时刻更好,就让s1保持,表示这之前都不跑而是来闪现
			s1 = s2;
		}
		if (s1 >= s) {
			cout << "Yes" << endl;
			cout << i << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	cout << s1;

文章来源:https://blog.csdn.net/m0_73553411/article/details/135080923
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。