SDOI 2015 立体図 ─ 巨大シミュレーション問題の攻略
この記事では、SDOI 2015の「立体図」問題の解法を詳しく解説します。この問題は、複雑な3Dブロックの描画と光のシミュレーションを要求する、難易度の高いシミュレーション問題です。
問題概要
この問題では、m×nのグリッド上に積まれた立方体の立体図を、複数の平行光源の下で描画します。各セルには高さ（積まれた立方体の数）が与えられ、最大9方向からの光（赤、緑 ...
8月5日 06:34 投稿
傾き最適化DP：Luogu P2365とSDOI2012タスクスケジューリング問題の解法
問題文
動的計画法の問題を考察します。便宜上、問題文中の費用係数を\\(v_i\\)で表現します。
\\(f_i\\)を第\\(i\\�\\)位置までの最適解と定義します。各遷移は、\\(i\\)番目に区間\\([j+1,i]\\)のコストを追加する操作です。
明らかに、累和を用いて最適化できます。しかし\\(s\\)の存在により、直接次元を追加してグループ数を記録すると大きなオーバーヘッドが発生し ...
6月17日 17:27 投稿