洛谷100題チャレンジ (5/100)
洛谷100題チャレンジ (5/100)
P1002 [NOIP2002 普及組] 馬避け - 洛谷 | コンピュータ科学教育新生態
long long型を使用しないと問題発生注意!!!
馬の制御点を全てマークし、残りは通常通り转移すればよい
\(dp[i][j] += dp[i - 1][j] + dp[i][j - 1]\)
\(i=0||j=0\)の場合、左または上からのみ转移可能
using i64 = long long;
using namespace std;
typedef pair Pair ...
7月16日 23:20 投稿
スキー問題の動的計画法解法
この問題は、2次元配列の最大下降子列を求める問題と理解できます。
解法
最も単純な方法は、直接のDFS（深度優先探索）です。問題がどこからスタートするかを指定していないため、各点をスタート点としてDFSを実行し、最大値を取得します。
本問題の正解は、メモ化検索と動的計画法（DP）の2種類があります。
メモ化検索
メモ化検索では、各点からスタートし、4つの ...
5月18日 14:20 投稿