---
# System prepended metadata

title: Untitled

---

pB 地鐵跑酷
Subtask 1 $M=1$
這個Subtask基本上是送分給大家，一排數字加起來就過了。
Subtask 2
令$dp[i][j][0/1]$表示前進了$i$單位，且現在正在第$j$條鐵軌上，$0/1$代表是否用過磁鐵，所能獲得最多的金幣數量。可以看出轉移式式這樣:
$dp[i][j][0]=max(dp[i-1][j-1][0],dp[i-1][j][0],dp[i-1][j+1][0])+w[i][j]$
$dp[i][j][1]=max(max(dp[i-1][j-1][0],dp[i-1][j][0],dp[i-1][j+1][0])+\Sigma_{k=1}^{M}w[i][k],$
$max(dp[i-1][j-1][1],dp[i-1][j][1],dp[i-1][j+1][1])+w[i][j])$
好好實作就可以AC了。
AC code:
```cpp=1
#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
const int MAXN=1E5+1;
int coin[MAXN][22], sum[MAXN], dp[MAXN][21][2];
int main(){ jizz
    int n,m;
    cin>>n>>m;
    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            cin>>coin[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            sum[i]+=coin[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            dp[i][j][0]=max(dp[i-1][j-1][0],max(dp[i-1][j][0],dp[i-1][j+1][0]))+coin[i][j];
            dp[i][j][1]=max(max(dp[i-1][j-1][0],max(dp[i-1][j][0],dp[i-1][j+1][0]))+sum[i],
                            max(dp[i-1][j-1][1],max(dp[i-1][j][1],dp[i-1][j+1][1]))+coin[i][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        ans=max(ans,dp[n][i][1]);
    }
    cout<<ans<<"\n";
    return 0;
}
```
pE 寶可夢養成日記
Subtask 1
BJ4
Subtask 2
基本上是Greedy，把(血量-攻擊力)由大到小排好後，取前$b$大使用第二種藥水就過了(當然要是正的)。
Subtask 3
搞不好可以爆搜之類的，不過我不會。
Subtask 4、5
這裡就要用到第二個Greedy，你會知道最好的做法永遠是對同一隻寶可夢用第一種藥水。所以最終做法就是枚舉對每一隻寶可夢使用所有第一種藥水的結果。時間複雜度為$O(NlogN)$。
AC code:
```cpp=1
#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
typedef pair<int,int> pii;
#define F first
#define S second
const int MAXN=2E5+1;
pii poke[MAXN];
bool cmp(pii p, pii q){
    return p.F-p.S>q.F-q.S;
}
int getmax(pii p){
    return p.F>p.S?p.F:p.S;
}
signed main(){ jizz
    int n,a,b;
    cin>>n>>a>>b;
    b=min(n,b);
    for(int i=0;i<n;i++){
        cin>>poke[i].F>>poke[i].S;
    }
    sort(poke, poke+n, cmp);
    int ans, res=0;
    for(int i=0;i<n;i++){
        if(i<b) res+=getmax(poke[i]);
        else res+=poke[i].S;
    }
    ans=res;
    if(b>0){
        int mul=(1<<a);
        for(int i=0;i<n;i++){
            if(i<b){
                ans=max(ans,res-getmax(poke[i])+poke[i].F*mul);
            } else{
                ans=max(ans,res-poke[i].S-getmax(poke[b-1])+poke[i].F*mul+poke[b-1].S);
            }
        }
    }
    cout<<ans<<"\n";
    return 0;
}

```
