当前位置:网站首页>POJ 3003 DP pathfinding record path

POJ 3003 DP pathfinding record path

2020-12-08 13:56:46 A kind of int_ Me

POJ 3003 DP Pathfinding Record path

I started with M Think of it as every a_i The upper limit of , This is fatal , Because of this question dfs Violent search + You can't cut branches because M<=40, All States have 2 To the 40th power of .

The exact solution is DP, set up dp[i][j] For in i It's about j High place , The minimum of the maximum height Spiderman has experienced , This dp[i][[j] It must be from dp[i - 1]j - x and dp[i - 1][j + x]( If j + x No more than 1000) Transferred . from dp[i - 1][j - x] If you transfer, it means that this step is up , Another representative is the next step , Transfer according to the corresponding rules ” The minimum of the maximum height experienced “ that will do , Last check dp[m][0] If there is a value, then .

About logging paths , This is for everyone dp[i][j], Record a pre[i][j] It means this step “ The height of the last step ”, At the end of the day dfs Just print it

AC Code

#include <stdio.h>
#include <string.h>

int n, t;
int aa[1005][1005];
int pr[1005][1005];

void b_print(int o, int x)
{
	if (o > 1)
	{
		b_print(o - 1, pr[o][x]);
	}
	printf(pr[o][x] < x ? "U" : "D");
}

int main()
{
	scanf("%d", &t);
	while (t--)
	{
		int i;
		int j;
		scanf("%d", &n);
		for (i = 0; i <= n; ++i)
		{
			for (j = 0; j <= 1000; ++j)
			{
				aa[i][j] = 99999999;
			}
		}
		for (j = 0; j <= 1000; ++j)
		{
			pr[1][j] = -1;
		}
		aa[0][0] = 0;
		for (i = 1; i <= n; ++i)
		{
			int xx;
			scanf("%d", &xx);
			for (j = 0; j <= 1000; ++j)
			{
				if (j + xx <= 1000 && aa[i - 1][j + xx] < aa[i][j])
				{
					aa[i][j] = aa[i - 1][j + xx];
					pr[i][j] = j + xx;
				}
				if (j - xx >= 0 && aa[i - 1][j - xx] < aa[i][j] && aa[i][j] > j)
				{
					aa[i][j] = aa[i - 1][j - xx] < j ? j : aa[i - 1][j - xx];
					pr[i][j] = j - xx;
				}
			}
		}
		if (aa[n][0] == 99999999)
		{
			printf("IMPOSSIBLE");
		}
		else
		{
			b_print(n, 0);
		}
		printf("\n");
	}
	return 0;
}

版权声明
本文为[A kind of int_ Me]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/20201208135614229m.html