最新要闻

广告

手机

“我能幸免吗?”妈妈因它离世,如今姑姑也确诊!医生:家族史≠遗传史丨门诊实录

“我能幸免吗?”妈妈因它离世,如今姑姑也确诊!医生:家族史≠遗传史丨门诊实录

特斯拉最美工程师宣布离职 加入特斯拉联合创始人创办的公司

特斯拉最美工程师宣布离职 加入特斯拉联合创始人创办的公司

家电

【题解】洛谷 P1002 [NOIP2002 普及组] 过河卒

来源:博客园


(资料图)

原题链接

解题思路

这是一道经典的动态规划题目。

如果尝试使用深度优先搜索(dfs)或广度优先搜索(bfs)做就会获得 TLE (注意数据范围)。于是我们想到了更为高级的动态规划(Dynamic Programming, dp)。

简略介绍动态规划算法的核心思想:把原问题分解为相对简单的子问题的方式求解复杂问题。与递推有几分相似?递推其实是动态规划的一个分支!

在求解动态规划这一类问题时,一般有三步:

1.状态的表示

在这道题目中,可以使用一个二维数组 dp[n][m] 来存放每一个子问题的答案,即用 dp[i][j] 来表示到达第i行第j列所需的最多步数,dp[n][m] 也就是答案了。

2.设立边界条件

由于过河卒初始就在第0列第0行,所以 dp[0][0] = 1;而他只能向下走或向右走,当在第0行或第0列时,情况只有1种。

3.状态转移方程

动态规划一类题目中的最关键部分。过河卒只能向下走或向右走,故 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

注意:还要注意马可以到达的地方,过河卒不能到达。

代码实现

1 #include 2 using namespace std; 3 const int N = 25; 4 const int dir[][2] = { 5     {1, 2}, {1, -2}, {2, 1}, {2, -1}, 6     {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1} 7 }; 8 long long dp[N][N]; 9 int n, m, sx, sy;10 bool vis[N][N];11 int main() {12     cin >> n >> m >> sx >> sy;13     vis[sx][sy] = true;14     for (int i = 0; i < 8; i ++){15         int tx = sx + dir[i][0];16         int ty = sy + dir[i][1];17         if (tx >= 0 && tx <= n && ty >= 0 && ty <= m)18             vis[tx][ty] = true;19     }20     dp[0][0] = 1;21     for (int i = 0; i <= n; i ++)22         for (int j = 0; j <= m; j ++)23             if (!vis[i][j]){24                 if (i) dp[i][j] += dp[i - 1][j];25                 if (j) dp[i][j] += dp[i][j - 1];26             }27     cout << dp[n][m];28     return 0;29 }

关键词: