$黑魔法訓練營 DP 習題題解.md

黑魔法訓練營 DP 題解既 Q&A

這是所有簡報裡的習題的程式碼，我會盡量寫的簡潔一點，想要看其他實作方法的話可以參考 這裡 喔！

沒回答到的問題

不遺褕立

謝謝妳的發言。

為什麼頭髮顏色那麼怪？

我原本要染紫色，但是頭髮太黑太粗顏色上不去就變成漂完的顏色了。 也可以說我被染髮劑抓到想要當假紫人（CodeForces Rating 顏色）。

講師聲音好好聽ㄛ

謝謝 ><

聽不懂的話可以在這裡（sli.do）問爆講師

可以！或是各種聯絡方式敲講師問問題都可以喔。

ig 勒

@fh.virus ，想要主帳的再私訊我 ><

有 cp 嗎

卡 cp

我還沒有，歡迎大家幫我湊 ><

收到的bl單可以分享嗎

10 count、banana fish、yuri on ice、世界第一初戀、純情羅曼史、我讓最想被擁抱的男人給威脅了、super lovers、獨佔我的英雄、given被贈與的未來、呼吸過度、寶石商人理查德的謎鑑定、天涯客、山河令、佐佐木與宮野、同級生、黑湖妖潭、如果30歲還是處男，似乎就能成為魔法師、做我的狗、森林裡的熊先生、戀愛禁區、我的室友帥哥學長、我才沒有哭、Free(? 感謝大家分享 ><

sc 真ㄉ聽起來好油ㄛ

好油

1384 的 PS 寫的是什麼意思？

抱歉，貼錯連結

不知道自己看簡報時，應該按右箭頭還是往下的

往下到沒有簡報時再往右喔。

我是升高一的學生，這是為厲害的學姊們設計的活動，不用顧慮我

不要這麼悲傷啦 >< 有什麼想問的都可以再問喔！

ATC-DP-pF.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	string s, t;
	cin >> s >> t;

	int n = s.size();
	int m = t.size();

	// 轉成 1-base
	s = ' ' + s;
	t = ' ' + t;

	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
	// 因為要回溯解答，所以要紀錄轉移的來源！
	// 1: (i-1, j), 2: (i, j-1), 3: (i-1, j-1)
	vector<vector<int>> sc(n + 1, vector<int>(m + 1, 0));

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (s[i] == t[j]) {
				dp[i][j] = dp[i-1][j-1] + 1;
				sc[i][j] = 3;
			} else if (dp[i-1][j] > dp[i][j-1]) {
				dp[i][j] = dp[i-1][j];
				sc[i][j] = 1;
			} else {
				dp[i][j] = dp[i][j-1];
				sc[i][j] = 2;
			}
		}
	}

	string ans;
	int i = n, j = m;
	while (sc[i][j] != 0) {
		if (sc[i][j] == 3) {
			ans.push_back(s[i]);
			i -= 1;
			j -= 1;
		} else if (sc[i][j] == 1)
			i -= 1;
		else
			j -= 1;
	}

	reverse(begin(ans), end(ans));

	cout << ans << '\n';

	return 0;
}

CSES1145.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	vector<int> x(n + 1, 0);
	for (int i = 1; i <= n; ++i)
		cin >> x[i];

	// O(n log n) 的作法狀態不太一樣
	// dp[i][j] 代表 x_1 ~ x_i 項的所有 increasing subsequence 裡
	// 長度為 j 的 IS 結尾最小可以是多少
	// 有點 greedy 的感覺
	
	vector<int> dp(n + 1, INT_MAX);
	dp[0] = 0;

	for (int i = 1; i <= n; ++i) {
		// dp 一定是遞增的，
		// 所以可以二分搜最早可以接上的位置
		int p = lower_bound(begin(dp), end(dp), x[i]) - begin(dp);
		dp[p] = x[i];
	}

	int ans = 0;
	// 記得判斷 ans + 1 會戳出去的狀況
	while (ans < n and dp[ans + 1] != INT_MAX)
		ans += 1;

	cout << ans << '\n';

	// 試著把過程畫出來看看吧！
	return 0;
}

CSES1629.cpp

#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> pii;
int solve(int n, vector<pii>& events) {
	sort(begin(events), end(events),
		[](pii a, pii b) {
			return a.second < b.second;
	});
	int ans = 0, cur_r = 0;
	for (int i = 0; i < n; ++i)
		if (events[i].first >= cur_r) {
			cur_r = events[i].second;
			ans += 1;
		}
	return ans;
}
 
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
 
	int n;
	cin >> n;
 
	vector<pii> events(n);
	for (int i = 0; i < n; ++i)
		cin >> events[i].first >> events[i].second;
 
	cout << solve(n, events) << '\n';
 
	return 0;
}

TIOJ1019.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve() {
	int N;
	cin >> N;

	// 底下兩個人相減的時候會超過 int 範圍
	// 所以記得開 long long ！
	vector<ll> d(N + 1);
	for (int i = 1; i <= N; ++i)
		cin >> d[i];

	vector<ll> dp(N + 1, 0);
	for (int i = 2; i <= N; ++i) {
		dp[i] = dp[i-1] + abs(d[i] - d[i-1]);
		if (i-2 >= 1)
			dp[i] = min(dp[i], dp[i-2] + abs(d[i] - d[i-2]));
	}

	cout << dp[N] << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T;
	cin >> T;

	// 那個不是箭頭喔！
	// 是 T-- > 0 的意思
	// 不過看起來很漂亮
	while (T --> 0)
		solve();

	return 0;
}

TIOJ1072.cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;

	while (cin >> n and n != 0) {
		vector<pii> ec(n);

		for (int i = 0; i < n; ++i)
			cin >> ec[i].second >> ec[i].first;

		sort(begin(ec), end(ec), greater<pii>());

		int sum = 0, ans = 0;
		for (int i = 0; i < n; ++i) {
			sum += ec[i].second;
			// 最後吃完的不一定是最後一個拿到餐點的
			// 記得要全部人取最大值
			ans = max(ans, sum + ec[i].first);
		}

		cout << ans << '\n';
	}

	return 0;
}

TIOJ1288.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) {
			cin >> a[i][j];
		}
	}

	// 使用 vector 宣告的時候可以指定初始值是誰
	// 如果用 int dp[][]; 在 main() 裡面宣告的話，
	// 記得要清空！
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) {
			dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
		}
	}

	int ans = 0;
	for (int j = 1; j <= n; ++j) {
		ans = max(ans, dp[n][j]);
	}

	cout << ans << '\n';

	return 0;
}

TIOJ1337.cpp

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int solve(int N, vector<pii>& segs, int lim) {
	int ans = 0;
	// 會有重複的右界，記得用 multiset
	multiset<int> rbs;
	for (const auto& [l, r]: segs) {
		while (!rbs.empty() and *begin(rbs) <= l)
			rbs.erase(begin(rbs));
		rbs.insert(r);
		// 如果太多了就移除最右邊的
		if ((int) rbs.size() > lim) {
			rbs.erase(prev(end(rbs)));
			ans += 1;
		}
	}
	return ans;
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int N, K;
	cin >> N >> K;

	vector<pii> segs(N);
	// 神奇語法
	for (auto &[l, r]: segs)
		cin >> l >> r;

	sort(begin(segs), end(segs));

	// 二分搜最小值
	int lb = 0, rb = N - K, mid;
	while (lb < rb) {
		mid = (lb + rb) / 2;
		// 如果最大值要 <= mid 會需要打掉超過 K 顆的隕石
		if (solve(N, segs, mid) > K)
			lb = mid + 1;
		else
			rb = mid;
	}

	cout << lb << '\n';

	return 0;
}

TIOJ1387.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	vector<int> w(n), m(n), c(n);

	for (int i = 0; i < n; ++i)
		cin >> w[i] >> m[i] >> c[i];

	int T;
	cin >> T;

	// 一樣要記得設定初始值為 0 ！
	vector<int> dp(T + 1, 0);

	for (int i = 0; i < n; ++i) {
		// 當成有 c[i] 個一樣的東西
		// 重複加入 c[i] 次就好了！
		for (int j = 0; j < c[i]; ++j) {
			for (int k = 0; k + w[i] <= T; ++k) {
				dp[k] = max(dp[k], dp[k + w[i]] + m[i]);
			}
		}
	}

	cout << dp[0] << '\n';

	return 0;
}

TIOJ1388.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;

	while (cin >> n) {
		vector<int> a(n + 1);
		for (int i = 1; i <= n; ++i)
			cin >> a[i];

		vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, 0ll));
		for (int i = 1; i <= n; ++i)
			dp[i][i] = a[i];

		for (int r = 2; r <= n; ++r) {
			for (int l = r - 1; l >= 1; --l) {
				for (int m = l; m < r; ++m) {
					if ((r - l + 1) % 2 == 1)
						dp[l][r] = max(dp[l][r], dp[l][m] * dp[m+1][r]);
					else
						dp[l][r] = max(dp[l][r], dp[l][m] + dp[m+1][r]);
				}
			}
		}

		cout << dp[1][n] << '\n';
	}

	return 0;
}

TIOJ1861.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	// 最小值 heap
	priority_queue<int, vector<int>, greater<int>> pq;

	while (cin >> n) {
		for (int a, i = 0; i < n; ++i) {
			cin >> a;
			pq.push(a);
		}

		long long ans = 0; 
		while (pq.size() > 1) {
			int a = pq.top(); pq.pop();
			int b = pq.top(); pq.pop();
			ans += a + b;
			pq.push(a + b);
		}

		cout << ans << '\n';

		// 記得清空
		pq.pop();
	}

	return 0;
}

TIOJ2223.cpp

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, M;
	cin >> n >> M;

	vector<pii> pw(n);
	for (int i = 0; i < n; ++i)
		cin >> pw[i].second >> pw[i].first;

	// 從大到小排序
	sort(begin(pw), end(pw), greater<pii>());

	int ans = 0;
	for (int i = 0; i < n; ++i) {
		// 神奇語法
		auto [p, w] = pw[i];
		int take = min(w, M);
		M -= take;
		ans += p * take;
		if (M == 0) break;
	}

	cout << ans << '\n';

	return 0;
}

UVa12405.cpp

#include <bits/stdc++.h>
using namespace std;

int solve() {
	int n;
	cin >> n;

	string s;
	cin >> s;

	int ans = 0;

	for (int i = 0; i < n; ++i)
		if (s[i] == '.') {
			ans += 1;
			i += 2;
		}

	return ans;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int T;
	cin >> T;

	// UVa 上面的題目很多輸出格式都很醜
	// 能不要碰就不要碰
	for (int t = 1; t <= T; ++t) {
		cout << "Case " << t << ": ";
		cout << solve() << '\n';
	}

	return 0;
}

ZJg278.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;

	vector<int> a(n + 1);
	for (int i = 1; i <= n; ++i)
		cin >> a[i];

	// can_go[i]: 以 i 為右界，一個合法區間最左邊可以到哪
	vector<int> last_id(n + 1, 0);
	vector<int> can_go(n + 1, 1);
	for (int i = 1; i <= n; ++i) {
		can_go[i] = max(can_go[i-1], last_id[a[i]] + 1);
		last_id[a[i]] = i;
	}

	// dp[i][j]: 已經選了 i 個區間，這些區間最右邊不超過 j
	// 這些區間的長度和最大值，底下有滾動，但是不滾也會過
	// 可以證明以一個點為右界，我拿到合法的最左邊一定不虧
	vector<int> dp(n + 1, 0), sc(n + 1, 0);
	for (int i = 0; i < k; ++i) {
		for (int j = 1; j <= n; ++j) {
			dp[j] = max(dp[j-1], sc[can_go[j] - 1] + (j - can_go[j] + 1));
		}
		swap(dp, sc);
	}

	// 最後會被多 swap 一次
	cout << sc[n] << '\n';
	return 0;
}