# POJ 3003 DP pathfinding record path

2020-12-08 13:56:46

### 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;
}
``````

https://chowdera.com/2020/12/20201208135614229m.html