# 前言
怎麼說呢，後面兩題是圖論+DP，我不知道我沒有報到名算不算一件好事:thinking:
# [P1 機械鼠](https://zerojudge.tw/ShowProblem?problemid=m370)
## 題目
有$n$個位置上有食物，另外有一隻老鼠一開始位於位置$x$。
老鼠在開始覓食前要選擇今天要往左邊或往右移動去尋找食物，經過食物時可以停下來吃食物，吃完後可以選擇繼續往相同方向移動，或者是結束今天的覓食。
請問老鼠最多能吃到多少個食物，以及最後停下來吃食物的位置。
## 解析
由於是第一題，我盡量使用簡單的字彙表達
首先，我們可以先假設一個數列已經排序好，我們要找的是
比$x$大和比$x$小的個數，取兩個的最大值 *(題目有保證不會等於)*
那最後位置呢?
一定是排序最後一個(right>left)或第一個(right<left)
好邏輯搞懂了，那麼實作吧!
## 程式碼
C++
時間複雜度$O(NlogN)$
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main()
{
a6isweak;//IO優化，這題可加可不加
int a[25];
int x,n;
cin>>x>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
int lit=0,big=0;
for(int i=0;i<n;i++)
{
if(a[i]<x) lit++;
else big++;
}
cout<<max(big,lit)<<' ';
if(big>lit)
cout<<a[n-1];
else
cout<<a[0];
return 0;
}
```
****
# [P2 卡牌遊戲](https://zerojudge.tw/ShowProblem?problemid=m371)
## 題目
你有一個 $n×m$ 大小的表格，你可以從中消除具有相同數值且之間沒有障礙物的兩個元素，並獲得分數。請問你可以獲得的最大得分。
每一種數字在表格中出現恰好兩次。消除兩個相同的數字 $x$ 時，可以獲得 $x$ 分。
消除規則：你可以垂直或水平地將兩個相同數值的元素消除，但消除的兩個元素之間不能有其他尚未消除的元素
## 解析
看到 $n≦20,m≦40$ 可以知道 時間複雜度最大可以來到$O(N^3)$，所以我只要實際下去做就會過了
你要先做橫的或是直的都可以，答案是一樣的，我這裡是示範先橫後直
## 程式碼
C++
時間複雜度看起來好像$O(N^3)$，但其實不到$O(N^3)$
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define N 25
#define M 35
int main()
{
a6isweak;
int a[N][M];
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>a[i][j];
}
bool bl=1;
int sum=0;
while(bl)
{
bl=0;
for(int i=0;i<n;i++)
{
int wnf=-1,z=0;
for(int j=0;j<m;j++)
{
if(a[i][j]==-1) continue;
if(a[i][j]!=-1&&wnf==a[i][j])
{
sum+=wnf;
a[i][j]=-1;
a[i][z]=-1;
wnf=-1;
bl=1;
}
else if(wnf==-1||a[i][j]!=wnf)
{
wnf=a[i][j];
z=j;
}
}
}
for(int j=0;j<m;j++)
{
int wnf=-1,z=0;
for(int i=0;i<n;i++)
{
if(a[i][j]==-1) continue;
if(a[i][j]!=-1&&wnf==a[i][j])
{
sum+=wnf;
a[i][j]=-1;
a[z][j]=-1;
wnf=-1;
bl=1;
}
else if(wnf==-1||a[i][j]!=wnf)
{
wnf=a[i][j];
z=i;
}
}
}
}
cout<<sum;
}
```
****
# [P3 搬家](https://zerojudge.tw/ShowProblem?problemid=m372)
## 題目
忍者龜住在下水道中，他們正在準備搬家。下水道由$n×m$的矩陣表示，其中不同的字元代表著水管的開口方向。如果兩個水管可以互相連接，它們屬於同一個連通塊。你需要找出最大的連通塊的大小。
其中，X 代表十字架，而 H、I、F、7、L 分別代表其他不同形狀的水管。0 字元代表沒有水管連接的地方。
請注意，在某個連通塊內的水管可以連接，而不同連通塊的水管不會相互連接。
下面是一些可能的水管形狀：
水管的開口方向與字元對應關係
F: 右和下
H: 左和右
7: 左和下
I: 上和下
X: 上、下、左和右
L: 右和上
J: 左和上
0: 沒有水管
## 解析
一看到這題直覺就是DFSorBFS了，事實上，這就是這題的正解，但問題來了，要選擇誰?
首先，我們分析一下兩個差異
BFS:迴圈，相對難寫
DFS:遞迴，相對好寫
那我知道了，肯定是選DFS!
答案恰恰相反，首先，會遇到遞迴深度可能不夠的問題(現在很少卡這個了)，再來記憶體可能會不夠(因為要宣告很多東西)，在無法送出執行的情況下，只好選擇相對不好寫的BFS下去做了
## 程式碼
**這裡借鑑了吳邦一教授的程式碼**
~~主要是因為我知道這題要寫很多判斷式，有點懶惰~~
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int visited[510][510]={0};//開全域，否則會有爆掉的風險
bool east(char ch) {
return ch=='H' || ch=='L' || ch=='F' || ch=='X';
}
bool west(char ch) {
return ch=='H' || ch=='J' || ch=='7' || ch=='X';
}
bool south(char ch) {
return ch=='I' || ch=='7' || ch=='F' || ch=='X';
}
bool north(char ch) {
return ch=='I' || ch=='L' || ch=='J' || ch=='X';
}
int main()
{
a6isweak;
int m,n,i,j;
string mat[510];
cin>>m>>n;
for (i=0;i<m;i++) cin >> mat[i];
int imax=0, t;
for (i=0;i<m;i++) for (j=0;j<n;j++) {
if (mat[i][j]=='0' || visited[i][j]) continue;
// BFS
vector<pair<int,int>> qu;
int head=0;
qu.push_back({i,j});
visited[i][j] = 1;
while (head < qu.size()) {
int r=qu[head].first, c=qu[head].second;
head++;
if (c<n-1 && !visited[r][c+1] && east(mat[r][c]) && west(mat[r][c+1])) {
qu.push_back({r,c+1});
visited[r][c+1] = 1;
}
if (c>0 && !visited[r][c-1] && west(mat[r][c]) && east(mat[r][c-1])) {
qu.push_back({r,c-1});
visited[r][c-1] = 1;
}
if (r<m-1 && !visited[r+1][c] && south(mat[r][c]) && north(mat[r+1][c])) {
qu.push_back({r+1,c});
visited[r+1][c] = 1;
}
if (r>0 && !visited[r-1][c] && north(mat[r][c]) && south(mat[r-1][c])) {
qu.push_back({r-1,c});
visited[r-1][c] = 1;
}
}
imax = max(imax,(int)qu.size());
}
cout<<imax;
return 0;
}
}
```
****
# [P4 投資遊戲](https://zerojudge.tw/ShowProblem?problemid=m373)
## 題目
你擁有一個長度為$n$的陣列，代表每天的投資收益，以及$k(k≦20)$張金牌。
你可以自行決定投資的開始和結束日期。在你選擇投資的每一天，你可以選擇消耗一張金牌來跳過當天，或者不使用金牌而拿取當天的收益。你的目標是找出如何投資，以實現最大的總收益。
請注意，你只能在投資期間進出一次。
## 解析(子題1,2)
在沒有k的限制下，這題可以變成一個greedy題目或是分治，其實就是熟知的最大連續子陣列。
在吳邦一教授的書中說:
「這就像一代一代累積財產，若爸媽給的是正總資產，則繼承過來，否則就拋棄繼承」
*~~雖然不符合民法，但教授說的永遠是對的~~*
## 程式碼(子題1,2)
*ZJ測資不好，會給50%*
C++(greedy)
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main() {
// for k=0
a6isweak;
int n,k;
cin>>n>>k;
int sum=0,ans=0;
for(int i=0;i<n;i++)
{
int z;
cin>>z;
if(sum>=0)
sum+=z;
else
sum=z;
ans=max(ans,sum);
}
cout<<ans;
return 0;
}
```
人生總是要有點目標，沒有目標總有夢想吧，所以我們來看有K的情況
## 解析
首先我們繼續思考，greedy到底可不可以?
想想看，如果要greedy首先要知道，我們是可以決定開始時間，那麼我們要枚舉開始時間和結束時間，還要找到最好的可能，最壞的情況時間複雜度甚至會到$O(k×n^2)$，那這條路應該行不通，所以這時候我們就會想到DP(動態規劃)
這個問題會是$2D1D$的DP，時間複雜度降到$O(k×n)$，在$k$不大的情況下，很接近$O(n)$，這題便是如此，順便說一聲，這種情況稱為「偽多項式時間複雜度」。
講了這麼多，我們其實只確定了做法。
我們知道DP最困難的就是列出遞迴關係式了，這裡，我們可以設立一個陣列$d[n]$，$d[i]$表示前面$i$個的最佳解，可是在有金牌的時候，可能會改變最佳解，既然這樣不行，我就加條件，我改成$d[n][k]$，$d[i][j]$表示前面$i$個，用了$j$個金牌的最佳解，這樣就可以列式了!
### 當$j=0$時
$d[i][0]=max(d[i-1][0],0)+a[i]$
### 當$j>0$時
在第$i$天時，我們可以選擇用金牌或不用，找最好的
$d[i][j]=max(d[i-1][j]+v[i],d[i-1][j-1])$
往往dp難在列式，程式碼大多都是a piece of cake!
## 程式碼
C++
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define maker a6
#define a6isweak ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int a[150005],d[150005][25];
int main() {
// for k!=0
a6isweak;
int n,k;
cin>>n>>k;
for(int i=0;i<n;i++)
cin>>a[i];
d[0][0]=a[0];
for(int i=1;i<n;i++)
d[i][0]=max(d[i-1][0],0)+a[i];
for(int j=0;j<=k;j++)
{
if(a[0]>0)
{
d[0][j]=a[0];
}
else
d[0][j]=0;
for(int i=1;i<n;i++)
{
d[i][j]=max(d[i-1][j]+a[i],d[i-1][j-1]);
}
}
int ans=0;
for(int i=0;i<n;i++)
ans=max(d[i][k],ans);
cout<<ans;
return 0;
}
```
# 心得
最後還是把這個題解弄出來了，這次我想考試時我應該寫不出來後面兩題，不過我覺得最後一題解出來的成就感很爽，這是我第一篇題解，而且寫最後一題的時候已經超過腦袋斷線時間了，如果有錯誤，麻煩私訊我DC，我看到的時候會改的!
DC:a6a6a6#5797
Sign in with Wallet
Connect another wallet