当前位置：网站首页>nyoj 712 Exploring treasure

nyoj 712 Exploring treasure

2022-08-08 18:57:00 【51CTO】

探寻宝藏

1000 ms | 内存限制： 65535

传说HMH大沙漠中有一个M*N迷宫,里面藏有许多宝物.某天,Dr.Kong找到了迷宫的地图,他发现迷宫内处处有宝物,最珍贵的宝物就藏在右下角,迷宫的进出口在左上角.当然,Pathways in a maze are not flat,到处都是陷阱.Dr.KongDecided to let his robot Kado go on an expedition.

But when the robot cardo goes from the upper left corner to the lower right corner,Only go down or to the right.When going back from the lower right corner to the upper left corner,Only go up or to the left,And Cardo isn't going back.（即：一个点最多经过一次）.Of course, Cardo also took every treasure along the way.

Dr.KongI hope his robot Kaduo can bring out as many treasures as possible.请你编写程序,帮助Dr.Kong计算一下,How many treasures can Cardo bring out at most.

第一行： K 表示有多少组测试数据.

Next, test data for each set：

第1行: M N

第2~M+1行： Ai1 Ai2 ……AiN (i=1,…..,m)

【约束条件】

2≤k≤5 1≤M, N≤50 0≤Aij≤100 (i=1,….,M; j=1,…,N)

All data are integers. 数据之间有一个空格.

输出对于每组测试数据,输出一行：Robot Cardo carries the most valuable treasures 样例输入

样例输出

来源第六届河南省程序设计大赛

上传者 ACM_赵铭浩

This question is the same as what we have done in the pastdp不同之处就在于 go and go

Join only go 我们可以 Use dynamic programming equations dp[i][j]=max(dp[i-1][j],dp[i][j-1])+map[i][j].

And this question went and came back We can understand that two people go from the upper left corner at the same time But don't go the same way

If two people don't go the same way Then the two people must not be in the same column or row 又因为 Both people take the exact same number of steps

So we can get the number of steps taken by another person through the number of steps taken by one person

We can store it through a four-dimensional array

So this time the dynamic programming equation

       
       dp[i][j][k][l]=max(max(dp[i-1][j][k-1][l],dp[i-1][j][k][l-1]),
       
29.
       
max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]))+map[i][j]+map[k][l];
      
1.
2.
3.

附上代码：

       
       #include <stdio.h>
       
       #include <string.h>
       
       #include <algorithm>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       map[
       
       55][
       
       55];  
       
       int 
       
       dp[
       
       55][
       
       55][
       
       55][
       
       55];
       
       int 
       
       main()
       
{
       
       int 
       
       ncase;
       
       scanf(
       
       "%d",
       
       &
       
       ncase);
       
       while(
       
       ncase
       
       --)
       
  {
       
       int 
       
       n,
       
       m;
       
       memset(
       
       dp,
       
       0,
       
       sizeof(
       
       dp));
       
       memset(
       
       map,
       
       0,
       
       sizeof(
       
       map));
       
       scanf(
       
       "%d %d",
       
       &
       
       m,
       
       &
       
       n);
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++)
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       n;
       
       j
       
       ++)
       
       scanf(
       
       "%d",
       
       &
       
       map[
       
       i][
       
       j]);
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++)
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       n;
       
       j
       
       ++)
       
       for(
       
       int 
       
       k
       
       =
       
       i
       
       +
       
       1;
       
       k
       
       <=
       
       m;
       
       k
       
       ++)
       
        {
       
       int 
       
       l
       
       =
       
       i
       
       +
       
       j
       
       -
       
       k;
       
       if(
       
       l
       
       <
       
       0
       
       ||
       
       l
       
       >
       
       n)
       
       break;
       
       dp[
       
       i][
       
       j][
       
       k][
       
       l]
       
       =
       
       max(
       
       max(
       
       dp[
       
       i
       
       -
       
       1][
       
       j][
       
       k
       
       -
       
       1][
       
       l],
       
       dp[
       
       i
       
       -
       
       1][
       
       j][
       
       k][
       
       l
       
       -
       
       1]),
       
       max(
       
       dp[
       
       i][
       
       j
       
       -
       
       1][
       
       k
       
       -
       
       1][
       
       l],
       
       dp[
       
       i][
       
       j
       
       -
       
       1][
       
       k][
       
       l
       
       -
       
       1]))
       
       +
       
       map[
       
       i][
       
       j]
       
       +
       
       map[
       
       k][
       
       l];
       
        }
       
       printf(
       
       "%d\n",
       
       max(
       
       max(
       
       dp[
       
       m][
       
       n
       
       -
       
       1][
       
       m
       
       -
       
       1][
       
       n],
       
       dp[
       
       m][
       
       n
       
       -
       
       1][
       
       m][
       
       n
       
       -
       
       1]),
       
       max(
       
       dp[
       
       m
       
       -
       
       1][
       
       n][
       
       m
       
       -
       
       1][
       
       n],
       
       dp[
       
       m
       
       -
       
       1][
       
       n][
       
       m][
       
       n
       
       -
       
       1]))
       
       +
       
       map[
       
       m][
       
       n]);
       
  }
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.

Because the space occupied by the four-dimensional array is particularly large And because in this question two people take exactly the same number of steps 也就是i+j=k+l So we can pass the step count 转换为3维的

dp[k][i][j] 其中kis the current number of steps taken ito the left of the row for the first person jis the row coordinate of the second person

And because the coordinates of the upper left corner of the map I created are （1,1） So the minimum number of steps required to go from the upper left corner to the lower right corner is m+n-2

The dynamic transition equation at this time is

       
       dp[k][i][j]=max(max(dp[k-1][i-1][j],dp[k-1][i-1][j-1]),
       
max(dp[k-1][i][j],dp[k-1][i][j-1]))+map[i][k-i+2]+map[j][k-j+2];
      
1.
2.
3.

ac代码：

       
       #include <stdio.h>
       
       #include <string.h>
       
       #include <algorithm>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       map[
       
       55][
       
       55];  
       
       int 
       
       dp[
       
       110][
       
       55][
       
       55];
       
       int 
       
       main()
       
{
       
       int 
       
       ncase;
       
       scanf(
       
       "%d",
       
       &
       
       ncase);
       
       while(
       
       ncase
       
       --)
       
  {
       
       int 
       
       n,
       
       m;
       
       memset(
       
       dp,
       
       0,
       
       sizeof(
       
       dp));
       
       memset(
       
       map,
       
       0,
       
       sizeof(
       
       map));
       
       scanf(
       
       "%d %d",
       
       &
       
       m,
       
       &
       
       n);
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++)
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       n;
       
       j
       
       ++)
       
       scanf(
       
       "%d",
       
       &
       
       map[
       
       i][
       
       j]);
       
       int 
       
       step
       
       =
       
       m
       
       +
       
       n
       
       -
       
       2;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <=
       
       m;
       
       i
       
       ++)
       
       for(
       
       int 
       
       j
       
       =
       
       i
       
       +
       
       1;
       
       j
       
       <=
       
       m;
       
       j
       
       ++)  
       
       for(
       
       int 
       
       k
       
       =
       
       1;
       
       k
       
       <
       
       step;
       
       k
       
       ++)
       
        {
       
       if(
       
       k
       
       +
       
       2
       
       >=
       
       i
       
       &&
       
       k
       
       +
       
       2
       
       >=
       
       j)
       
          {
       
       dp[
       
       k][
       
       i][
       
       j]
       
       =
       
       max(
       
       max(
       
       dp[
       
       k
       
       -
       
       1][
       
       i
       
       -
       
       1][
       
       j],
       
       dp[
       
       k
       
       -
       
       1][
       
       i
       
       -
       
       1][
       
       j
       
       -
       
       1]),
       
       max(
       
       dp[
       
       k
       
       -
       
       1][
       
       i][
       
       j],
       
       dp[
       
       k
       
       -
       
       1][
       
       i][
       
       j
       
       -
       
       1]))
       
       +
       
       map[
       
       i][
       
       k
       
       -
       
       i
       
       +
       
       2]
       
       +
       
       map[
       
       j][
       
       k
       
       -
       
       j
       
       +
       
       2];
       
          }
       
        }
       
       printf(
       
       "%d\n",
       
       max(
       
       dp[
       
       step
       
       -
       
       1][
       
       m][
       
       m
       
       -
       
       1],
       
       dp[
       
       step
       
       -
       
       1][
       
       m
       
       -
       
       1][
       
       m])
       
       +
       
       map[
       
       m][
       
       n]);
       
  }
       
       return 
       
       0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.