読者です 読者をやめる 読者になる 読者になる

SRM 658 DIV1 Med: Mutalisk

/*

思いつき方
二分探索
チェック関数を書く
bool のDPになった。
boolのDPは次元を一つ減らせるかも。
intで残りの1を使える回数の最大値をもたせればいい。
*/
/*
dp[i][j][k]
:=
i番目まで破壊し、残りj回9の攻撃、k回3の攻撃ができるとき、残りの1の攻撃回数の最大値
*/

/*
K回の攻撃でOKか調べたい。

ある要素に対して
S = 9を使った回数 + 3を使った回数 + 1を使った回数 <= K
でなければならない。
S > K
とすると、
K+1回以上の操作が必要になってしまう。
S<=K
とすると、残りの操作回数は他に配ればいい。これはDPの条件そのまま。
*/