蒟蒻用dp过了,但有个奇怪的问题
查看原帖
蒟蒻用dp过了,但有个奇怪的问题
728740
qimingli楼主2023/3/12 21:28

有个奇怪的问题 虽然AC了,但还是不太明白

使用动态规划,代码如下:

#include<stdio.h>
#include<stdlib.h>
#define min(a,b) (a<b)?a:b
#define INF 1e9
int val[205];
int step[201][201];//step[i][j]从i 到j的最小次数
int main()
{
	int n, sou, des;
	scanf("%d%d%d", &n, &sou, &des);
	int i, j, k;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i != j)
				step[i][j] = INF;
			else
				step[i][j] = 0;
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &val[i]);
		if (val[i] == 0)
			continue;
		int j = i + val[i];
		int k = i - val[i];
		if (j <= n)
			step[i][j] = 1;
		if (k >= 1)
			step[i][k] = 1;
	}
	int t;
	for (t = 1; t <= 50; t++)
	{
		for (i = 1; i <= n; i++)
		{
			for (j = n; j >= 1; j--)
			{
				for (k = 1; k <= n; k++)
				{
					step[i][j] = min(step[i][j], step[i][k] + step[k][j]);
				}
			}
		}
	}
	

	if (step[sou][des] != INF)
		printf("%d", step[sou][des]);
	else
		printf("-1");
	return 0;
}

注意
在循环这里有四层,但是最外层只有25次,如果没有这层循环的话,代码会WA两个点#9 #10,但是这层循环的意义不是很懂
向大佬求教

2023/3/12 21:28
加载中...