---
title: ABC_285_E - Work or Rest
tags: 題單
disqus: hackmd
---

# ABC_285_E - Work or Rest

[題目連結](https://atcoder.jp/contests/abc285/tasks/abc285_e)

題目大意：
如果一個星期有 $N$ 天，你可以決定一個星期要放幾天假，請問一個禮拜的最高生產力是多少。

注意事項：
- 每個禮拜都是一樣的（放的天數與第幾天都一樣）
- 一個禮拜至少要放一天

生產力的算法：
- 有一個數列 $A$ ( $a_1$, $a_2$, $a_3$ ... )
- 若第 $i$ 天離前後的放假日各為 $m, n$ 天，則第 $i$ 天的生產力為 $a_{min(m, n)}$
- 若第 $i$ 天放假，則生產力為 0

## 解法

[官方解答](https://atcoder.jp/contests/abc285/editorial/5541)

在官方解答下面有別人的解，我覺得很神奇，所以記錄一下。

### 先將一個禮拜處理一下

因為每個禮拜的排法都一樣，所以我們可以將其頭尾相接形成一個環
因為是環，所以在哪切開都還是環，對最佳解沒有影響

-> 所以我們可以把其中一個假日移到一個禮拜的開頭

### 接著分組

我們再將一個禮拜以假日做分組
假日當開頭，後面接上到下個假日為止的工作日
因為至少有一個假日，所以至少會有一組

如下圖
橘色代表假日，藍色是工作日，綠色為一組


### 計算生產力

先來看看生產力的規律，我將它設為數列 $P$，若上述一組有 $i$ 天，生產力為 $P_i$

$P_1 = 0$ （只有假日）
$P_2 = a_1$
$P_3 = a_1 + a_1$
$P_4 = 2a_1 + a_2$
$P_5 = 2a_1 + a_2 + a_2$
$P_6 = 2a_1 + 2a_2 + a_3$
依此類推...

有了規律就可以在 $O(N)$ 算出 $P$ 了

### 神奇的時刻來了

前面做了這麼多就是為了這一刻
我們把問題變成了這樣：
- 在 $N$ 天裡用 $P$ 將它填滿並填出最多的生產力

怎麼~~一個不小心~~就變成無限背包問題了
- 背包有 $N$ 的容量
- 每件物品的重量與價值是 $(i, P_i)$

這樣就可以用背包問題來解了