P1

題敘

詳細題述
給一棵樹
每個點有點權
求每個邊至少一個點被選中的最小值
n,m <= 2e5 , a[i]<=100

思路

經典樹dp題, 秒了

程式碼

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
vector<int> adj[N];
int a[N];
int vis[N],dp[N][2];
void dfs(int u){
    dp[u][1]+=a[u];
    for(int v:adj[u]){
        if(vis[v]) continue;
        vis[v]=1;
        dfs(v);
        dp[u][1] += min(dp[v][0],dp[v][1]);
        dp[u][0] += dp[v][1]; 
    }
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vis[1]=1;
    dfs(1);
    cout << min(dp[1][0],dp[1][1]) << '\n';
}

P2

題敘

詳細題述

給一個n*m個格子
每個格子上下左右的街道會給一個值（-100~100)
只能走左右、下，不能重複走
問從任意起點
走到
任意終點的最大值

思路

跟之前的 勇者修練 很像,
總之就是一道經典的方格圖dp
我們先定義dp[i][j][0/1/2]為 走到i,j時最後從上往下/左往右/右往左 的最大值
首先因為不能往上走,所以我們一定是從上算下來,然後又不能重複走
所以同一列往左走的一定不會跟往右走的有關,反之亦然
我們只要從左掃一遍再從右掃一遍就可以了
詳細轉移可以看程式碼理解

程式碼

#include <bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int g[N][N][4];
// R,D,L,U
int dp[N][N][3];
int main(){
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<n;j++){
            int v;
            cin>>v;
            g[i][j][0] = g[i][j+1][2] = v;
        }
    }
    for(int i=1;i<m;i++){
        for(int j=1;j<=n;j++){
            int v;
            cin>>v;
            g[i][j][1] = g[i+1][j][3] = v;
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            dp[i][j][0] = max({
                dp[i-1][j][0]+g[i-1][j][1],
                dp[i-1][j][1]+g[i-1][j][1],
                dp[i-1][j][2]+g[i-1][j][1],
                0
            });
            dp[i][j][1] = max({
                dp[i][j-1][0]+g[i][j-1][0],
                dp[i][j-1][1]+g[i][j-1][0],
                0
            });
        }
        for(int j=n;j>=1;j--){
            dp[i][j][2] = max({
                dp[i][j+1][0]+g[i][j+1][2],
                dp[i][j+1][2]+g[i][j+1][2],
                0
            });
        }
    }
    int ans = -1e9;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            ans = max({ans,dp[i][j][0],dp[i][j][1],dp[i][j][2]});
        }
    }
    cout << ans << '\n';
}

P3

題敘

詳細題述
給一個1～9的字串
再中間插入幾個+ 求 <m 的最大值跟方法數
|S| <=40 , m<=3e4

思路

uhhh因為前面兩題都是dp所以我這題完全沒想過dp
有想過折半枚舉但我不會寫
最後只寫了一般的枚舉,大概40分吧

程式碼

#include <bits/stdc++.h>
using namespace std;
string s;
int n,m;
int ans=0;
int cnt=0;
void rec(int idx,int cur){
    if(idx==n){
        if(cur>ans){
            ans=cur;
            cnt=1;
        }
        else if(cur==ans){
            cnt++;
        }
        return;
    }
    int ccr=0;
    for(int i=idx;i<n;i++){
        ccr = ccr*10+(s[i]-'0');
        if(cur+ccr>m) break;
        rec(i+1,cur+ccr);
    }
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>s>>m;
    n = s.size();
    rec(0,0);
    cout << ans << '\n' << cnt << '\n';
}

結尾

我都拿 AACPOJ 測試過了
拿了 255/300 分
希望APCS測資爛一點讓我能賽到250分((
等我11/13更新這裡ouob