Codeforces #408 (Div. 2) E: Exam Cheating

dp[i][j][fs][sc]

=i番目まの問題まで確定していて、j回カンニングしている。1人目に対して直前にしたカンニングの左端はiからfs個左、2人目に対して直前にしたカンニングの左端はiからsc個左とする。ただし、fs,scはK以上はすべてKの1値で表す。このとき最大の得点。

この愚直なDPの計算量は

O(n*p*k^2)

n*p*k^2≦1000*1000*50^2 = 2.5*10^9

で間に合わない。

もっと容易に解が求まる場合を考えてみる。

2人対してすべての問題をカンニングできる場合を考える。

この場合は

p≧2*ceil(n/k)

と同値。このとき得点しうる問題はすべて得点できる。

そうでない場合は

p<2*ceil(n/k)

が成り立つ。

このとき

O(n*p*k^2)

= O(n*(n/k)*k^2)

= O(n^2 * k)

となり、間に合う。

計算量が多いのは解が自明なケースであった。解が自明なケースを場合分けで切り離して計算量を落とす。
広告を非表示にする