CEOI 2018 Day 1

https://csacademy.com/contest/ceoi-2018-day-1/summary/

Cloud Computing

https://csacademy.com/contest/ceoi-2018-day-1/task/cloud-computing/

問題

周波数f_{i}のコアc_{i}個をv_{i}円で仕入れることができる。 周波数F_{i}以上のコアC_{i}個をV_{i}円で購入する注文がくる。 各注文は受けても受けなくてもいい。 最大の利益はいくらか。

メモ

dp[][i] : コアi個余っている時の最大の利益、というdpで解ける。 https://csacademy.com/submission/1710230

Global Warming

https://csacademy.com/contest/ceoi-2018-day-1/task/global-warming/

問題

数列が与えられる。 数列の任意の区間d(-x \leq d \leq x)を足すことができる。 LISの最大値を求めよ。

メモ

任意の区間に足す必要はなくi以降の要素に足すとしてよい。 Benqの解を参考にした。

https://csacademy.com/submission/1715714

Lottery

問題

メモ

Benqの解を参考にした。 Javaで2次元配列用意するとMLEになってしまうので1次元配列に潰した。

https://csacademy.com/submission/1716086