디도스

Claim. 공격의 총 위력을 최대화하는 해 중, 다음 성질을 만족하는 것이 존재한다.

• 어떤 시각 $t \in \{1, 2, \dots, k\}$가 존재해, 시각 $t$에 공격할 수 있는 컴퓨터는 모두 시각 $t$에 공격한다.

Proof. 어떠한 최적해에 대해, 그러한 $t$가 존재하지 않는다고 가정하자. 가장 많은 수의 컴퓨터가 공격하는 시각 중 하나를 $t_{max}$라 하자. 이때, 가정에 의해, $t_{max}$에 공격할 수 있지만 공격하지 않는 컴퓨터 $x$가 있다. 해당 컴퓨터가 공격하는 시각을 $t_x$라 하고, 시각 $t_{max}$와 $t_x$에 공격하는 컴퓨터의 수를 각각 $c_{max}$와 $c_x$라 하자.

이때, 컴퓨터 $x$가 공격하는 시각을 $t_{max}$로 바꾸면 더 나은 해가 됨을 보인다. 이 변화로 인해 생기는 공격의 총 위력의 변화량은

$$\begin{aligned} \left((c_{max}+1)^2+(c_x-1)^2 \right) - (c_{max}^2 + c_x^2) = 2(c_{max} - c_x) + 2 \end{aligned}$$

$t_{max}$의 정의에 의해 $c_{max} \ge c_x$이므로, 위 식의 값은 항상 양수이다. 따라서, 현재 해가 최적해라는 가정이 잘못되었고, 귀류법에 의해 원래 명제가 성립한다.

이제 위 성질과 동적 계획법을 이용해 문제를 해결한다. $D$를 다음과 같이 정의하자.

• $D[l][r]$: 공격할 수 있는 시각의 범위가 $[l, r]$에 포함되는 컴퓨터만 고려했을 때, 총 공격 위력의 최댓값

위 성질은 어떤 $[l, r]$에 대해 공격 시각 범위가 $[l, r]$에 포함되는 컴퓨터들만 고려해도 성립한다. 따라서, 어떤 시각 $t$를 골라, 해당 시각에 공격할 수 있는 모든 컴퓨터는 해당 시각에 공격하게 할 수 있다. 이를 이용하면, 다음과 같은 점화식을 세울 수 있다.

$$DP[l][r] = \max_{l \le t \le r} \left( DP[l][t-1] + f(l, r, t)^2 + DP[t+1][r] \right)$$

단, $l > r$일 때 $DP[l][r] = 0$으로 정의하며, $f(l, r, t)$는 공격 시각이 $[l, r]$에 포함되는 컴퓨터 중 시각 $t$에 공격할 수 있는 컴퓨터의 수를 나타낸다. 따라서, $f(l, r, t)$를 $O(1)$에 구할 수 있는 방법이 있다면, 위 풀이를 이용해 $O(k^3)$에 문제를 해결할 수 있을 것이다.

어떤 컴퓨터의 공격 시각 범위가 $[l_i, r_i]$일 때, 해당 컴퓨터의 공격 시각이 $[l, r]$에 포함되고, 시각 $t$에 공격할 수 있을 조건은, $l \le t \le r$의 가정 아래 다음과 같이 생각할 수 있다.

• $l \le l_i \le t$
• $t \le r_i \le r$

위 두 조건이 모두 만족하는 경우에만 $i$번 컴퓨터가 $f(l, r, t)$에 $1$만큼의 기여를 할 것이다. 위 조건은 $(l_i, r_i)$의 2차원 누적합을 통해 구할 수 있고, 이는 $O(n+k^2)$ 시간에 전처리해줄 수 있다. 따라서 문제를 $O(n+k^3)$에 해결할 수 있다.