【蓝桥杯冲冲冲】[NOIP2000 提高组] 方格取数

蓝桥杯备赛 | 洛谷做题打卡day19

• [NOIP2000 提高组] 方格取数

  题目背景

  NOIP 2000 提高组 T4

  题目描述

  设有 $N\times N$ 的方格图 $(N\le 9)$，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 $0$。如下图所示（见样例）:

  

  某人从图的左上角的 $A$ 点出发，可以向下行走，也可以向右走，直到到达右下角的 $B$ 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 $0$）。
  此人从 $A$ 点到 $B$ 点共走两次，试找出 $2$ 条这样的路径，使得取得的数之和为最大。

  输入格式

  输入的第一行为一个整数 $N$（表示 $N\times N$ 的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的 $0$ 表示输入结束。

  输出格式

  只需输出一个整数，表示 $2$ 条路径上取得的最大的和。

  样例 #1

  样例输入 #1

  8
  2 3 13
  2 6  6
  3 5  7
  4 4 14
  5 2 21
  5 6  4
  6 3 15
  7 2 14
  0 0  0
  

  样例输出 #1

  67
  

  提示

  数据范围：$1\le N\le 9$。

题解代码

学会利用新知，自己多试试并尝试积攒一些固定解答方案，debug，以下是题解代码 ~

#include<iostream>
    using namespace std;
    int N=0;
    int s[15][15],f[11][11][11][11];
int dfs(int x,int y,int x2,int y2)//两种方案同时执行，表示当第一种方案走到x,y,第二种方案走到x2,y2时到终点取得的最大数 
{
    if (f[x][y][x2][y2]!=-1) return f[x][y][x2][y2];//如果这种情况已经被记录过了，直接返回，节省时间 
    if (x==N&&y==N&&x2==N&&y2==N) return 0;//如果两种方案都走到了终点，返回结束 
    int M=0;
    //如果两种方案都不在最后一列，就都往下走，统计取得的数，如果有重复，就减去一部分 
    if (x<N&&x2<N) M=max(M,dfs(x+1,y,x2+1,y2)+s[x+1][y]+s[x2+1][y2]-s[x+1][y]*(x+1==x2+1&&y==y2));
    //如果第一种方案不在最后一行，第二种方案不在最后一列，第一种就向下走，第二种就向右走， 
    //统计取得的数，如果有重复，就减去一部分
    if (x<N&&y2<N) M=max(M,dfs(x+1,y,x2,y2+1)+s[x+1][y]+s[x2][y2+1]-s[x+1][y]*(x+1==x2&&y==y2+1));
    //如果第一种方案不在最后一列，第二种方案不在最后一行，第一种就向右走，第二种就向下走， 
    //统计取得的数，如果有重复，就减去一部分
    if (y<N&&x2<N) M=max(M,dfs(x,y+1,x2+1,y2)+s[x][y+1]+s[x2+1][y2]-s[x][y+1]*(x==x2+1&&y+1==y2));
    //如果第一种方案和第二种方案都不在最后一列，就都向右走，统计取得的数，如果有重复，就减去一部分
    if (y<N&&y2<N) M=max(M,dfs(x,y+1,x2,y2+1)+s[x][y+1]+s[x2][y2+1]-s[x][y+1]*(x==x2&&y+1==y2+1));
    //对最后那个 s[x][y+1]*(x==x2&&y+1==y2+1))的解释：这个是用来判断两种方案是不是走到了同一格的
    //如果是真，就返回1，否则返回0，如果是1的话，理所当然的可以减去s[x][y+1]*1,否则减去s[x][y+1]*0相当于
    //不减,写得有点精简，省了4个if，见谅哈~ 
    f[x][y][x2][y2]=M;//记录这种情况 
    return M;//返回最大值 
}
int main()
{
    cin>>N;
    //将记录数组初始化成-1，因为可能出现取的数为0的情况，如果直接判断f[x][y][x2][y2]!=0（见dfs第一行）
    //可能出现死循环而导致超时，细节问题 
    for(int a=0;a<=N;a++)
      for(int b=0;b<=N;b++)
        for(int c=0;c<=N;c++)
          for(int d=0;d<=N;d++) f[a][b][c][d]=-1;
    for(;;)//读入 
    {
        int t1=0,t2=0,t3=0;
        cin>>t1>>t2>>t3;
        if(t1==0&&t2==0&&t3==0) break;
        s[t1][t2]=t3;
    }
    cout<<dfs(1,1,1,1)+s[1][1];//输出，因为dfs中没有考虑第一格，即s[1][1]，所以最后要加一下 
    return 0;
}

我的一些话

• 今天来巩固动态规划dp，多思考思路还是很好掌握的，虽然一次性AC有一定难度，需要通盘的考虑和理解，以及扎实的数据结构基础才能独立写出AC代码。但无论难易，大家都要持续做题，保持题感喔！一起坚持(o´ω`o)

• 如果有非计算机专业的uu自学的话，关于数据结构的网课推荐看b站上青岛大学王卓老师的课，讲的很细致，有不懂都可以私信我喔

• 总结来说思路很重要，多想想，多在草稿纸上画画，用测试数据多调试，debug后成功编译并运行出正确结果真的会感到很幸福！

• 关于之前蓝桥杯备赛的路线和基本方法、要掌握的知识，之前的博文我都有写，欢迎大家关注我，翻阅自取哦~

• 不管什么都要坚持吧，三天打鱼两天晒网无法形成肌肉记忆和做题思维，该思考的时候一定不要懈怠，今天就说这么多啦，欢迎评论留言，一起成长：）