new article body
ABC100
D - Patisserie ABC
https://atcoder.jp/contests/abc100/tasks/abc100_d
アルゴリズム・データ構造
貪欲法、全探索
考察
全探索できるか?
→N(1000)個からM(500)個選ぶのがMAX計算量のため不可
選ぶ、選ばないでDPできる?
→現在の綺麗さ、美味しさ、人気度を保持する必要がある。x,y,xは-10**10-10**10のため不可
貪欲方でできないか?
→式からどのように優先順位をつけることが出来るかを考える
→絶対値があるため、マイナスをとった方がいいケースがある。
→各項目の最終値のプラマイで場合分けをすると貪欲に考えられる。
→3種類の項目なので2**3=8通りの全探索で貪欲法でいけそう
計算量
全探索 2**3=8
貪欲のためのsort NlogN
貪欲 M
提出
感想
絶対値が出てきた場合は場合分けできないかを検討するとよさそう。