中國(guó)資本網(wǎng) > 熱點(diǎn) > 正文
【題解】洛谷 P1002 [NOIP2002 普及組] 過(guò)河卒
2023-08-27 22:34:07來(lái)源: 博客園


(相關(guān)資料圖)

原題鏈接

解題思路

這是一道經(jīng)典的動(dòng)態(tài)規(guī)劃題目。

如果嘗試使用深度優(yōu)先搜索(dfs)或廣度優(yōu)先搜索(bfs)做就會(huì)獲得 TLE (注意數(shù)據(jù)范圍)。于是我們想到了更為高級(jí)的動(dòng)態(tài)規(guī)劃(Dynamic Programming, dp)。

簡(jiǎn)略介紹動(dòng)態(tài)規(guī)劃算法的核心思想:把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題。與遞推有幾分相似?遞推其實(shí)是動(dòng)態(tài)規(guī)劃的一個(gè)分支!

在求解動(dòng)態(tài)規(guī)劃這一類(lèi)問(wèn)題時(shí),一般有三步:

1.狀態(tài)的表示

在這道題目中,可以使用一個(gè)二維數(shù)組 dp[n][m] 來(lái)存放每一個(gè)子問(wèn)題的答案,即用 dp[i][j] 來(lái)表示到達(dá)第i行第j列所需的最多步數(shù),dp[n][m] 也就是答案了。

2.設(shè)立邊界條件

由于過(guò)河卒初始就在第0列第0行,所以 dp[0][0] = 1;而他只能向下走或向右走,當(dāng)在第0行或第0列時(shí),情況只有1種。

3.狀態(tài)轉(zhuǎn)移方程

動(dòng)態(tài)規(guī)劃一類(lèi)題目中的最關(guān)鍵部分。過(guò)河卒只能向下走或向右走,故 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

注意:還要注意馬可以到達(dá)的地方,過(guò)河卒不能到達(dá)。

代碼實(shí)現(xiàn)

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 }

關(guān)鍵詞:

相關(guān)新聞
專(zhuān)題新聞
  • LV推出充氣夾克多少錢(qián)?lv是什么檔次?
  • 三星手機(jī)業(yè)務(wù)換帥是哪一年?三星手機(jī)為什么撤出中國(guó)?
  • 股票配資是什么意思?個(gè)人做股票配資違法嗎?
  • 數(shù)據(jù)中心機(jī)房是干什么的?idc機(jī)房主要用于哪些工作?
  • 周樂(lè)偉接班董明珠真的嗎?格力集團(tuán)是世界500強(qiáng)企業(yè)嗎?
  • 小米技術(shù)委員會(huì)厲害嗎?米家是不是小米旗下的公司?

京ICP備2021034106號(hào)-51

Copyright © 2011-2020  亞洲資本網(wǎng)   All Rights Reserved. 聯(lián)系網(wǎng)站:55 16 53 8 @qq.com