AOJ0601ダイクストラ法なのですが、コストの持ち方を工夫する必要があります。memo[N] = 累計コスト+(木の高さ-現在位置)このように持つと、正しくダイクストラ法により解を求めることが出来ます。木の上下移動は最小限に抑える必要がありますが、木の距離か…

AOJに問題が登録されたので解いてみました。 AOJ0302予め星の輝きをソートしておきます。 ある星Aを決めると、(Aの輝き)以上かつ(Aの輝き+d)に最も近い星までが星座を作る星になるので、 その様に選んだ時の長方形の面積Sの大きさは S = (星座内で最も大きい…

更新は再帰的に処理します。各操作O(logN) ///RMQ #define SIZE (1<<18) #define ll long long #define INF (1<<30)///必要に応じて増やす ll int MSEG[SIZE]; void update(int index){ if(index==0)return; int l = index*2,r = index*2+1,tmp = MSEG[index…