# 2024/6/29 APCS 第六場模擬賽 題解
## 大智慧學苑-畢業旅行囉 (Trip)
> 出題者：Howard
> 難度：p1
> 考點：模擬
### Statement
已經到了六月，大智慧學苑正準備著學員們的畢業旅行，大智慧學苑院長 Chung 非常奇怪，和大部分學校不同的是他想要在畢業典禮後再舉辦畢業旅行，院長這次破例，想要幫所有學員出飛機票錢，但是他們要搭乘的航空公司有很多優惠，此優惠根據不同年齡層會有更動，給定 $n$ 個人，還有優惠的年齡區間 $L_i、R_i$ 優惠價，以及原價，請你寫程式告訴院長需要花多少錢。
若年齡未在所有優惠年齡區間，則以原價計算。
年齡層不可能會有重複。
### Input
第一行有兩個數字 $n,m\ (1\leq n\leq 1000,\ 10\leq m\leq 1000)$ 代表有 $n$ 位學員以及機票原價為 $m$
第二行有 $n$ 個數字 $a_1, a_2, a_3,...,a_n\ (1\leq a_i\leq 100)$ 代表每個人的年齡
第三行有一個數字 $k (1\leq k\leq 50)$ 代表有幾筆優惠
第四行開始總共有 $k$ 行，每行有三個數字 $L_i, R_i, P_i\ (1\leq L_i\leq R_i\leq 100,\ 1\leq P_i < m)$ 代表年齡從 $L_i$ (包含) 到 $R_i$ (包含) 的優惠價格為 $P_i$
### Output
輸出共一個數字代表院長需要付的所有機票錢。
### Testcase
- Input 1
```
5 100
7 10 5 20 15
3
5 10 50
1 3 10
20 30 60
```
- Output 1
```
310
```
### Subtask
- Subtask 1 (50%) - $k=1$
- Subtask 2 (50%) - 無其他限制
### Solution
- Subtask 1：由於只有一組 $L, R$ ，所以只要在全部輸入後再跑一次迴圈看看有哪些是符合優惠方案的，是的話就是用優惠方案的價錢，不是的話就用原機票價錢 $k$ 計算。
- Subtask 2：針對每個人都去試試看是否符合優惠方案的年齡區間，由於題目保證年齡區間不會重複，所以只要找到一個符合的區間就一定是那個答案。
### Code
- Subtask 1
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int k;
cin >> k;
int L, R, P;
cin >> L >> R >> P;
int ans = 0;
for(int i = 0; i < n; i++) {
if(a[i] >= L && a[i] <= R) ans += P;
else ans += m;
}
cout << ans << '\n';
return 0;
}
```
- Subtask 2
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int a[n];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int k;
cin >> k;
int L[k], R[k], P[k];
for(int i = 0; i < k; i++) {
cin >> L[i] >> R[i] >> P[i];
}
int ans = 0;
for(int i = 0; i < n; i++) {
bool used = 0;
for(int j = 0; j < k; j++) {
if(a[i] >= L[j] && a[i] <= R[j]) {
used = 1;
ans += P[j];
break;
}
}
if(!used) ans += m;
}
cout << ans << '\n';
return 0;
}
```
- Python by 橘子
```python=
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [m]*n
for _ in range(int(input())):
l,r,p = map(int,input().split())
for i in range(n):
if l<=a[i]<=r:
b[i] = min(b[i],p)
print(sum(b))
```
## 烤肉吧！ (barbecue)
> 出題者：Cheng
> 難度：p2
> 考點：二維陣列操作
### Statement
<center>
<img src="https://hackmd.io/_uploads/rJ9I9V6UC.png">
</center>
香噴噴又油亮亮的烤肉是 Cheng 的最愛呢！
在美好的夜晚當中，明亮的火光在你眼前，香氣撲鼻而來，好想大喊一句「バーベキューは最高！」
今天又在烤肉的 Cheng 想要烤出超美味的烤肉，於是依照路邊撿到的黑暗聖典來烤出美味的烤肉！
<center>
<img src="https://hackmd.io/_uploads/SJs5cNpLC.png">
</center>
<br>
我們可以把烤肉網和烤爐皆視為一個大小相同的 $n \times m$ 矩陣，烤爐一開始在第 $i$ 列第 $j$ 行會有 $H_{i,j}$ 的焰度，每分鐘結束時焰度會增加 $y_{i,j}$，(注意到 $y_{i,j}$ 可能是負的，所以烤爐的焰度可能會越來越低，但若低於 $0$ 皆須視為 $0$)。
Cheng 在烤肉網上放上了 $n \times m$ 塊肉，每塊大小恰等於烤肉網上的每一格，我們可以簡單的將肉劃分為正反兩面，肉正反兩面每格的熟度以及溫度初始為 $0$，每分鐘每個格子上的肉的溫度會加上火爐該格當時的焰度，格子上的肉正(反)面每吸收 $k$ 度，該格子上的肉正(反)面熟度就會增加 $1$。若每塊肉正反兩面的熟度都大於或等於 $R$，就代表所有肉都熟了！Cheng 就會把它們拿下來享用！
黑暗聖典的指示有兩種，每分鐘聖典都會有下列其中一種指示：
* $S$：把每塊肉翻面
* $.$：放著繼續烤
黑暗聖典上面說，只要時間一到就要馬上做該時間要做的操作，且因為 Cheng 的手腳很快，所以每分鐘 Cheng 會先操作完，肉再吸收烤爐焰度，也就是說每分鐘會依序執行：聖典操作 -> 烤爐加熱烤肉 -> 烤肉熟度改變 -> 烤爐更新焰度。
另外，烤肉把肉烤焦也是一件很正常的事，若肉的正(反)面熟度嚴格大於 $R \times 2$，則這塊肉的正(反)面會燒焦 (燒焦只是過熟，所以依然算熟)，為了驗證黑暗聖典的有用程度，Cheng 想要額外知道正面和反面總共有幾個格子上的肉燒焦 (正反面都要算一次，假如有 $3$ 個正面焦掉、有 $2$ 個反面焦掉，則總計為 $5$)。
Cheng 想知道在 $t$ 分鐘過後依照黑暗聖典的指示所有肉會不會熟，以及正面和反面總共有幾個格子上的肉燒焦了？(需要注意如果烤到一半就全熟了，則會直接被拿起來，不用等到 $t$ 分鐘結束)
大家一起開心的吃烤肉吧！
### Input
輸入第一行將有兩個整數 $n, m\ (1 \le n, m \le 10)$。
輸入第二行將有三個整數 $t\ (1 \le t \le 1000), k, R\ (1 \le k, R \le 500)$。
輸入第三行將有一個字串 $S\ (|S| = t,\ S$ 只會有 "S" 或 "." 兩種字元$)$ 代表黑暗聖典上說的操作 (字串第 $1$ 個字元代表第 $1$ 分鐘要做的操作)。
接著有 $n$ 行，每行會有 $m$ 個數字 $H_{i,j}\ (0 \le H_{i,j} \le 100)$，代表烤爐第 $i$ 列、第 $j$ 行初始的焰度。
輸入第一行將有兩個整數 $n, m\ (1 \le n, m \le 10)$。
輸入第二行將有三個整數 $t\ (1 \le t \le 1000), k, R\ (1 \le k, R \le 500)$。
輸入第三行將有一個字串 $S\ (|S| = t,\ S$ 只會有 "S" 或 "." 兩種字元$)$ 代表黑暗聖典上說的操作 (字串第 $1$ 個字元代表第 $1$ 分鐘要做的操作)。
接著有 $n$ 行，每行會有 $m$ 個數字 $H_{i,j}\ (0 \le H_{i,j} \le 100)$，代表烤爐第 $i$ 列、第 $j$ 行初始的焰度。
最後有 $n$ 行，每行會有 $m$ 個數字 $y_{i,j}\ (-10 \le y_{i,j} \le 10)$，代表第 $i$ 列、第 $j$ 行烤爐每分鐘會增加的焰度，請注意，烤爐焰度最低為 $0$，不會是負的。
### Output
輸出兩個數字，依序代表 $t$ 分鐘後所有烤肉有沒有都熟了 (輸出 $0$ 代表仍有肉沒熟、$1$ 代表所有肉正反每格都熟了)、正面和反面總共有幾個格子上的肉燒焦。(需要注意如果烤到一半就全熟了，則會直接被拿起來，不用等到 $t$ 分鐘結束)
### Testcase
- Input 1
```
2 2
3 5 5
...
70 35
80 2
8 10
8 6
```
- Output 1
```
0 3
```
- Input 1
```
2 2
3 5 5
.S.
5 80
12 17
6 5
0 -3
```
- Output 1
```
0 2
```
### Subtask
- Subtask 1 (50%) - $S$ 只由 "." 組成
- Subtask 2 (50%) - 無其他限制
### Note
每秒依序執行：聖典操作 -> 烤爐加熱烤肉 -> 烤肉熟度改變 -> 烤爐更新焰度
### Solution
可以發現這是個二維陣列操作的題目
我們要找到 $(i,j)$ 格到底累積了多少次 $k$ 溫度
我們可以將 $(i,j)$ 的溫度差除以 $k$ 來得知該時間點會増加多少熟度
(加上後整個會累積多少 $k$) $-$ (加上前累積了多少 $k$)
在每個時間點操作後都去檢查該塊肉是否熟了，熟了就直接拿下來計算燒焦區域有多少
其實 sub1 跟 sub2 的差別只是「記得將上層與下層的溫度做 swap 的動作 (翻面)」
### Code
- Subtask 1
```cpp=
void sol()
{
int n, m;
cin >> n >> m;
int t, k, R;
cin >> t >> k >> R;
vector<vector<vector<int>>> h(2, vector<vector<int>>(n, vector<int>(m, 0))), T(2, vector<vector<int>>(n, vector<int>(m, 0)));
int down = 0, top = 1;
vector<vector<int>> H(n, vector<int>(m)), y(n, vector<int>(m));
string s;
cin >> s;
for(auto &v : H) for(int &it : v) cin >> it;
for(auto &v : y) for(int &it : v) cin >> it;
int jiao = 0;
for(int time = 0; time < t; time++){
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
int dis = (h[down][i][j] + H[i][j])/k - h[down][i][j]/k;
h[down][i][j]+=H[i][j];
if(H[i][j] && dis) T[down][i][j]+=dis;
H[i][j]+=y[i][j], H[i][j] = max(0, H[i][j]);
}
bool check = 1;
for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(T[dir][i][j] < R) check = 0;
}
if(check){
for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(T[dir][i][j] > 2*R) jiao++;
}
cout << 1 << ' ' << jiao << '\n';
return;
}
}
for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(T[dir][i][j] > 2*R) jiao++;
}
cout << 0 << ' ' << jiao << '\n';
}
```
- Subtask 2
```cpp=
void sol()
{
int n, m;
cin >> n >> m;
int t, k, R;
cin >> t >> k >> R;
vector<vector<vector<int>>> h(2, vector<vector<int>>(n, vector<int>(m, 0))), T(2, vector<vector<int>>(n, vector<int>(m, 0)));
int down = 0, top = 1;
vector<vector<int>> H(n, vector<int>(m)), y(n, vector<int>(m));
string s;
cin >> s;
for(auto &v : H) for(int &it : v) cin >> it;
for(auto &v : y) for(int &it : v) cin >> it;
int jiao = 0;
for(int time = 0; time < t; time++){
if(s[time] == 'S') swap(down, top);
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
int dis = (h[down][i][j] + H[i][j])/k - h[down][i][j]/k;
h[down][i][j]+=H[i][j];
if(H[i][j] && dis) T[down][i][j]+=dis;
H[i][j]+=y[i][j], H[i][j] = max(0, H[i][j]);
}
bool check = 1;
for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(T[dir][i][j] < R) check = 0;
}
if(check){
for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(T[dir][i][j] > 2*R) jiao++;
}
cout << 1 << ' ' << jiao << '\n';
return;
}
}
for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
if(T[dir][i][j] > 2*R) jiao++;
}
cout << 0 << ' ' << jiao << '\n';
}
```
- Subtask 2 by Chung
```cpp=
#include<bits/stdc++.h>
using namespace std;
//declare
const int maxn = 15;
int n,m,t,k,R,cnt;
int H[maxn][maxn]; // 烤爐
int y[maxn][maxn]; // 焰度更新
int T[2][maxn][maxn]; // 兩面吸收的溫度
int M[2][maxn][maxn]; // 兩面熟度
string s;
//
int main(){
cin>>n>>m>>t>>k>>R>>s;
for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>H[i][j];
for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>y[i][j];
bool flag = 0;
for(int x=0;x<t;x++){
if(s[x] == 'S') flag ^= 1; // 聖典操作
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
// 烤爐加熱肉
T[flag][i][j] += H[i][j];
// 烤肉熟度改變
M[flag][i][j] = T[flag][i][j] / k;
// 烤爐更新焰度
H[i][j] += y[i][j];
H[i][j] = max(0, H[i][j]);
}
}
// 判斷是否全熟
bool ok = 1;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(M[0][i][j] < R) ok = 0;
if(M[1][i][j] < R) ok = 0;
}
}
// 計算焦掉的數量
cnt = 0; // 焦掉的數量
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cnt += (M[0][i][j] > 2*R);
cnt += (M[1][i][j] > 2*R);
}
}
if(ok){
cout<<1<<" "<<cnt<<"\n";
return 0;
}
}
cout<<0<<" "<<cnt<<"\n";
return 0;
}
```
- Python by 橘子
```python=
n, m = map(int,input().split())
t, k, r = map(int,input().split())
s = input()
h = [list(map(int,input().split())) for _ in range(n)]
d = [list(map(int,input().split())) for _ in range(n)]
down = [[0]*m for _ in range(n)]
up = [[0]*m for _ in range(n)]
ans1 = 0
for i in range(t):
if s[i]=='S':
down, up = up, down
ed = True
for x in range(n):
for y in range(m):
down[x][y] += h[x][y]
h[x][y] = max(0,h[x][y]+d[x][y])
if down[x][y]//k < r or up[x][y]//k < r:
ed = False
if ed:
ans1 = 1
break
ans2 = 0
for x in range(n):
for y in range(m):
ans2 += (down[x][y]//k>r*2)+(up[x][y]//k>r*2)
print(ans1,ans2)
```
## 蘋果樹 (Apple Tree)
> 出題者：Chung
> 難度：p3
> 考點：dfs/bfs、二分搜、前綴和
### Statement
Chung 家裡種了一棵蘋果樹，最近到了可以採收的季節，於是 Chung 決定來採收這些蘋果，為了方便，Chung 已經將樹枝用 $1 \sim n$ 進行編號 (其中樹幹編號必為 $1$)，且已經將在同個樹枝上的蘋果分類為同一組，並提供給你兩個資訊：每個樹枝連接的樹枝編號，每個樹枝上的蘋果數量。
因為 Chung 很懶惰，所以即使他有很多個籃子，卻只想要選定一個籃子來採收，但這樣就面臨了一個問題：如果採收的蘋果太少，Chung 就會覺得吃不飽，反之如果採收的蘋果太多又會造成浪費，所以他想要預先知道使用每個籃子分別可以採收多少蘋果。
Chung 會從樹幹開始採收，先採收和樹幹連接的那些樹枝們上的蘋果，再採收和那些樹枝們連接的樹枝們上的蘋果，以此類推一層一層往上採收，但是，假如採收完這一層之後就會讓籃子裝不下，那麼 Chung 就會放棄採收這一層並停止採收。
Chung 想要知道，使用每個籃子分別最高可以採收到第幾層，你能寫個程式幫幫他嗎？(樹幹為第 $0$ 層)
### Input
輸入第一行將有兩個整數 $n,m\ (1 \le n,m \le 2 \times 10^5)$，分別代表蘋果樹的樹枝數量和 Chung 擁有的籃子數量。
接著一行有 $m$ 個整數 $c_1,c_2,\dots,c_m\ (0 \le c_i \le 5 \times 10^6)$，分別代表第 $i$ 個籃子的容量 (至多可以裝的蘋果數量)。
接著會有 $n$ 行，第 $i\ (1 \le i \le n)$ 行第一個整數為 $k_i\ (1 \le k_i < n)$，代表有 $k_i$ 個樹枝和編號為 $i$ 的樹枝連接，緊接著有 $k_i$ 個整數 $x_{i,1},x_{i,2},\dots,x_{i,k_i}\ (1 \le x_{i,j} \le n,\ 1 \le j \le k_i)$，分別代表和編號 $i$ 的樹枝相連的樹枝編號，彼此之間用空白隔開。
最後一行有 $n$ 個整數 $a_1,a_2,\dots,a_n\ (0 \le a_i \le 1000)$，彼此用空白隔開，$a_i$ 代表編號為 $i$ 的樹枝上有幾顆蘋果 ($a_1$ 保證為 $0$)。
### Output
請總共輸出 $m$ 行，第 $i$ 行請輸出在使用第 $i$ 個籃子的情況下，Chung 最高可以採收到第幾層。
### Input Format
$n\ m$
$c_1\ c_2\ \dots c_m$
$k_1\ x_{1,1},x_{1,2},\dots,x_{1,k_1}$
$k_2\ x_{2,1},x_{2,2},\dots,x_{2,k_2}$
$\dots$
$k_n\ x_{n,1},x_{n,2},\dots,x_{n,k_n}$
$a_1\ a_2\ \dots a_n$
### Output Format
$ans_1$
$ans_2$
$\dots$
$ans_m$
### Testcase
- Input 1
```
6 4
0 6 8 21
2 2 3
1 1
4 1 4 5 6
1 3
1 3
1 3
0 1 6 2 7 5
```
- Output 1
```
0
0
1
2
```
### Subtask
- Subtask 1 (30%) - $n,m \le 1000$
- Subtask 2 (70%) - 無其他限制
### Solution
- Subtask 1
- 我們可以對於每筆詢問都做一次 bfs，基於 bfs 的性質，每次走訪到的點都是層層遞增，剛好符合求深度總和的需求。
- 題解使用到的技巧是「一次處理完同一深度的節點」，具體實作方式就是每次都一次處理完當前 queue 裡的節點，再依序將新的一層推進 queue，這樣就可以保證每次在 queue 中都是同深度的節點，這樣一來在計算同一層的總和時就會很方便。
- 總時間複雜度：$O(nm)$
- Subtask 2
- 觀察到每次的操作所求的資訊其實可以先被儲存起來
- 我們只需要維護各深度蘋果總和的前綴和，就可以針對每筆詢問二分搜到總和不超過容量的最大值，$O(\log n)$ 解決
- 題解使用 dfs 實作，並開一個陣列維護深度總和
- 總時間複雜度：$O(n+m \log n)$
### Code
- Subtask 1
```cpp=
#include<bits/stdc++.h>
using namespace std;
//declare
const int maxn = 2e5+5;
int n,m,c[maxn],cnt[maxn];
bool vis[maxn];
vector<int> G[maxn];
//
int bfs(int cap){
for(int i=1;i<=n;i++) vis[i] = 0;
queue<int> q;
q.push(1);
vis[1] = 1;
int sum = 0, depth = 0;
while(q.size()){
int sz = q.size();
for(int i=0;i<sz;i++){
int cur = q.front(); q.pop();
for(int adj : G[cur]){
if(vis[adj]) continue;
vis[adj] = 1;
sum += cnt[adj];
q.push(adj);
}
}
if(sum > cap) return depth;
depth++;
}
return depth-1;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++) cin>>c[i];
for(int i=1;i<=n;i++){
int k; cin>>k;
for(int j=0;j<k;j++){
int x; cin>>x;
G[i].push_back(x);
}
}
for(int i=1;i<=n;i++) cin>>cnt[i];
for(int i=0;i<m;i++){
cout<<bfs(c[i])<<"\n";
}
return 0;
}
```
- Subtask 2
```cpp=
#include<bits/stdc++.h>
using namespace std;
//declare
const int maxn = 2e5+5;
int n,m,c[maxn],depth[maxn],cnt[maxn],sum[maxn],max_depth;
bool vis[maxn];
vector<int> G[maxn], pre{0};
//
void dfs(int cur){
for(int adj : G[cur]){
if(vis[adj]) continue;
vis[adj] = 1;
depth[adj] = depth[cur] + 1;
dfs(adj);
}
sum[depth[cur]] += cnt[cur];
max_depth = max(max_depth, depth[cur]);
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++) cin>>c[i];
for(int i=1;i<=n;i++){
int k; cin>>k;
for(int j=0;j<k;j++){
int x; cin>>x;
G[i].push_back(x);
}
}
for(int i=1;i<=n;i++) cin>>cnt[i];
vis[1] = 1;
dfs(1);
for(int i=1;i<=max_depth;i++) pre.push_back(pre.back() + sum[i]);
for(int i=0;i<m;i++) cout<<upper_bound(pre.begin(),pre.end(),c[i]) - pre.begin() - 1<<"\n";
return 0;
}
```
- Python by 橘子
```python=
import bisect
n,m = map(int,input().split())
c = list(map(int,input().split()))
con = [[int(s)-1 for s in input().split()][1:] for _ in range(n)]
vis = [0]*n
a = list(map(int,input().split()))
v = []
x = [0]
y = []
vis[0] = 1
cur = 0
while x:
for i in x:
cur += a[i]
for j in con[i]:
if not vis[j]:
y.append(j)
vis[j] = 1
v.append(cur)
x = y
y = []
v.append(10**18)
for i in c:
print(bisect.bisect_left(v,i+1)-1)
```
## 活動 (Event)
> 出題者：C0DET1GER
> 難度：p4
> 考點：貪心、排序、動態規劃
### Statement
APCS 模擬測驗團隊雖然最初是為了舉辦模擬測驗而成立的，但後來因為大家的鼓勵、參與，模擬測驗團隊也開始有辦理其他活動的想法（例如：APCS Camp、實體 APCS 模擬測驗...）。
對於每一個活動，都會有一定的收益（因為 APCS 模擬測驗團隊是一個公益組織，收益有可能為 $0$，甚至是負的）和獲益人數。
APCS 模擬測驗團隊當然希望能夠讓越多人參與越好，但要考量到有些活動會帶來虧損，因此團隊想要在所有可能的舉辦方案中，選擇一個總收益 $\ge 0$ 的方案，且參與人數盡量大。
除此之外，因為時間上的問題，在 $N$ 個活動中至多只能舉辦 $K$ 個相互不重複的活動，否則團隊將會忙到焦頭爛額。
因此模擬測驗團隊希望你能夠幫幫忙，給定 $N$ 個活動的收益和參與人數，請求出在所有可能的舉辦方案中，在總收益 $\ge 0$ 的情況下參與人數總和的最大值（初始資金為 $0$）。
### Input
第一行輸入兩個正整數 $N$ $(1 \leq N \leq 35)$, $K$ $(1 \leq K \leq N)$
接下來輸入 $N$ 行，每一行包含兩個數字：$a_i$ $(-10^7 \leq a_i \leq 10^7)$和 $b_i$ $(0 \leq b_i \leq 100)$，分別代表第 $i$ 個活動的淨收益和獲益人數。
### Output
一個數字，代表 $K$ 個活動（按照任意順序進行）的最大可能收益人數總和。
### Testcase
- Input 1
```
5 3
-50 70
-70 80
100 10
-1 2
-100 100
```
- Output 1
```
110
```
### Subtask
- Subtask 1 (10%)：$N \leq 8$
- Subtask 2 (10%)：$N \leq 20$
- Subtask 3 (30%)：$|a_i| \leq 100$
- Subtask 4 (50%)：題目範圍限制
### Note
最佳解為：先取 3 再取 5。因為題目是說至多 $K$ 個活動，活動數量可以小於 $K$。
### Solution
（此處 $a_i$ 一律代表第 $i$ 個活動的淨收益，$b_i$ 代表第 $i$ 個活動的獲益人數
* Subtask 1：
* 先暴力枚舉要哪些活動再枚舉所有可能排列。
* 時間複雜度：$O(2^N \times N!)$
* Subtask 2：
* 先貪心的將活動按照 $a_i$ 排序再枚舉
* 時間複雜度：$O(N \log N + 2^N)$
* Subtask 3：
* 先貪心的將活動按照 $a_i$ 排序
* 這個 Subtask 開始要使用動態規劃。可以設計狀態 $dp[i][j][k]$，其中 $i$ 代表前 $N$ 個活動、$j$ 代表現在已經舉辦了幾個活動、$k$ 代表現在有多少錢、$dp[i][j][k]$ 代表在考慮前 $i$ 個活動之中辦了 $j$ 個活動、最後有 $k$ 塊錢的時候，參與人數最大可能值。
* 因為已經預先照 $a_i$ 排序，不會有因為順序錯誤而導致 DP 答案錯誤的問題
* 轉移：$dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k - a_i] + b_i)$
* 初始化：$dp[i][j][k] = 0$
* 答案：dp 陣列中的最大值
* 時間複雜度：$O(N^2 \times \sum{\max(a_i, 0)} )$
* Subtask 4：
* （人數至多跟 Subtask 3 的 profit 一樣大的提示應該夠大了吧）
* 先貪心的將活動按照 $a_i$ 排序
* 發現 $|a_i|$ 的範圍太大了，用原本的方法時間複雜度會炸開。但是可以改變狀態的定義。可以設計狀態 $dp[i][j][k]$，其中 $i$ 代表前 $N$ 個活動、$j$ 代表現在已經舉辦了幾個活動、$k$ 代表現在總共有多少人參與、$dp[i][j][k]$ 代表在考慮前 $i$ 個活動之中辦了 $j$ 個活動、來的人有 $k$ 個的時候，獲利的最大可能值。
* 轉移：$dp[i][j][k] = \max(dp[i - 1][j][k], dp[i - 1][j - 1][k - b_i] + a_i)$
* 要注意轉移中如果 $dp[i - 1][j - 1][k - b_i] < 0$，要直接把 $dp[i][j][k]$ 設為 $dp[i - 1][j][k]$
* 初始化：$dp[0][0][0] = 0$、$dp[i][j][k] = -1$
* 答案：在所有 $dp[i][j][k] \geq 0$ 中，$k$ 的最大可能值。
* 時間複雜度：$O(N^2 \times \sum{b_i})$
### Code
- Subtask 1
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int N, K;
cin >> N >> K;
vector<pair<int, int>> event(N);
for (int i = 0; i < N; i++){
cin >> event[i].first >> event[i].second;
}
int maximum = 0;
for (int i = 0; i < (1LL << N); i++){
vector<int> chosen;
for (int j = 0; j < N; j++){
if (i & (1 << j)){
chosen.push_back(j);
}
}
if (chosen.size() <= K){
do{
int money = 0, cnt = 0;
for (int j = 0; j < chosen.size(); j++){
money += event[chosen[j]].first;
if (money < 0){
break;
}
cnt += event[chosen[j]].second;
}
maximum = max(maximum, cnt);
}while (next_permutation(chosen.begin(), chosen.end()));
}
}
cout << maximum << "\n";
}
```
- Subtask 2
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b){
return a.first > b.first;
}
int main(){
int N, K;
cin >> N >> K;
vector<pair<int, int>> event(N);
for (int i = 0; i < N; i++){
cin >> event[i].first >> event[i].second;
}
sort(event.begin(), event.end(), cmp);
int maximum = 0;
for (int i = 0; i < (1LL << N); i++){
int money = 0, cnt = 0, used = 0;
for (int j = 0; j < N; j++){
if (i & (1 << j)){
money += event[j].first;
if (money < 0){
break;
}
cnt += event[j].second;
used++;
}
}
if (used <= K){
maximum = max(maximum, cnt);
}
}
cout << maximum << "\n";
}
```
- Subtask 3
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b){
return a.first > b.first;
}
int main() {
int N, K;
cin >> N >> K;
int sum = 0;
vector<pair<int, int>> event(N);
for (int i = 0; i < N; i++){
cin >> event[i].first >> event[i].second;
sum += max(event[i].first, 0);
}
sort(event.begin(), event.end(), cmp);
vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(K + 1, vector<int>(sum + 1, -1)));
dp[0][0][0] = 0;
int maximum = 0;
for (int i = 1; i <= N; i++){
for (int j = 0; j <= K; j++){
for (int k = 0; k <= sum; k++){
dp[i][j][k] = dp[i - 1][j][k];
if (j != 0 && k >= event[i - 1].first && k <= (sum + event[i - 1].first) && dp[i - 1][j - 1][k - event[i - 1].first] >= 0){
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - event[i - 1].first] + event[i - 1].second);
}
maximum = max(maximum, dp[i][j][k]);
}
}
}
cout << maximum << "\n";
}
```
- Subtask 4
``` cpp=
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(pair<int, int> a, pair<int, int> b){
return a.first > b.first;
}
int main() {
int N, K;
cin >> N >> K;
int sum = 0;
vector<pair<int, int>> event(N);
for (int i = 0; i < N; i++){
cin >> event[i].first >> event[i].second;
sum += event[i].second;
}
sort(event.begin(), event.end(), cmp);
vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(K + 1, vector<int>(sum + 1, -1)));
dp[0][0][0] = 0;
int maximum = 0;
for (int i = 1; i <= N; i++){
for (int j = 0; j <= K; j++){
for (int k = 0; k <= sum; k++){
dp[i][j][k] = dp[i - 1][j][k];
if (j != 0 && k >= event[i - 1].second && dp[i - 1][j - 1][k - event[i - 1].second] >= 0){
dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - event[i - 1].second] + event[i - 1].first);
}
if (dp[i][j][k] >= 0){
maximum = max(maximum, k);
}
}
}
}
cout << maximum << "\n";
}
```
- 折半枚舉 by 橘子
```python=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
int main(){
ios::sync_with_stdio(0);cin.tie(0);
ll n,k;
cin >> n >> k;
vector<pair<ll,ll>> a(36,{0,0});
for(ll i = 0;i<n;i++) cin >> a[i].first >> a[i].second;
n = 36;
sort(a.begin(),a.end());
vector<pair<ll,ll>> b(1<<18,{0,0});
vector<vector<pair<ll,ll>>> c(19);
ll ans = 0;
for(ll i = 1;i<(1<<18);i++){
b[i] = b[i-(i&-i)];
ll j = __builtin_ctzll(i);
b[i].first += a[j].first;
b[i].second += a[j].second;
ll cnt = __builtin_popcountll(i);
if(cnt<=k&&b[i].first>=0) ans = max(ans,b[i].second);
if(cnt<k){
for(ll w = cnt;w<=18;w++)c[w].push_back(b[i]);
}
}
for(auto &o : c){
sort(o.begin(),o.end());
for(ll i = o.size()-2;i>=0;i--){
o[i].second = max(o[i].second,o[i+1].second);
}
}
vector<pair<ll,ll>> d(1<<18,{0,0});
for(ll i = 1;i<(1<<18);i++){
d[i] = d[i-(i&-i)];
ll j = __builtin_ctzll(i);
d[i].first += a[j+18].first;
d[i].second += a[j+18].second;
ll cnt = __builtin_popcountll(i);
if(cnt<=k&&d[i].first>=0) ans = max(ans,d[i].second);
if(cnt<k&&k-cnt<=18){
auto &o = c[k-cnt];
if(o.empty()) continue;
auto it = lower_bound(o.begin(),o.end(),make_pair(-d[i].first,0ll));
if (it!=o.end()){
ans = max(ans,d[i].second+(*it).second);
}
}
}
cout << ans << "\n";
}
```
- Python by 橘子
```python=
def main():
n, k = map(int,input().split())
a = [tuple(map(int,input().split())) for _ in range(n)]
a.sort(reverse=True)
dp = [[-10**10]*3505 for _ in range(k+1)]
dp[0][0] = 0
ed = [0]*(k+1)
for x, y in a:
for i in range(k,0,-1):
ed[i] = max(ed[i],ed[i-1]+y)
arr1 = dp[i]
arr2 = dp[i-1]
for j in range(y,3502):
arr1[j] = max(arr1[j],arr2[j-y]+x)
ans = 0
for j in range(k,0,-1):
arr = dp[j]
for i in range(ed[j],ans,-1):
if arr[i]>=0:
ans = max(ans,i)
print(ans)
main()
```
Sign in with Wallet
Connect another wallet