Try   HackMD

學測後復建 練題

學測後太久沒寫題目，開個筆記紀錄一下復健過程。順便寫寫看沒寫過的AP325，後面AP325沒東西寫就隨便寫了

這份筆記是復健用，而且題目也沒很難，所以我就不像以前一樣打想法了，實作code也打得比較隨興，沒有整理。

本次練習用彰化精誠中學的judge。但這個網站題目沒有很完整，後面有些東西會去其他解題網站練習，例如TIOJ、UVA、Sprout OJ(neoj)之類的

目前累積44題

可以複習的題目

P-6-8 : local alignment
TIOJ 1092 : topological sort
TIOJ 1290 : dijkstra
UVa 10986 : dijkstra
UVA 11015 : Floyd-Warshall
UVa 558 : SPFA負環判斷

P-1-1

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a135





























































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


int f();
int g();

int main(){
	char c;
	cin >> c;
	if(c == 'f'){
		cout << f() <<'\n';
	}
	else{
		cout << g() << '\n'; 
	}
} 

int f(){
	int x;
	string s;
	cin >> s;
	if(s== "f"){
		x = f();
	}
	else if(s == "g"){
		x = g();
	}
	else{
		x = stoi(s);
	}
	return 2* x-1;
}
int g(){
	int x, y;
	string s;
	cin >> s;
	if(s== "f"){
		x = f();
	}
	else if(s == "g"){
		x = g();
	}
	else{
		x = stoi(s);
	}
	
	cin >> s;
	if(s== "f"){
		y = f();
	}
	else if(s == "g"){
		y = g();
	}
	else{
		y = stoi(s);
	}
	
	return x + 2 * y - 3;
}

P-1-3

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a133
















































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

int p[50005];
int cost = 0;

int search(int l, int r, int x){
	int k = l;
	for(int i = (r - l) / 2; i > 0; i /= 2){
		while(k + i < r and p[k+i] <= x){
			k += i;
		}
	}
	if(p[k] - p[l] < p[r] - p[k+1]){
		k ++;
	}
	return k;
}

void f(int l, int r){
	if(r -l <= 1){
		return;
	}

	int pp = search(l, r, (p[r] + p[l]) / 2);

	if(pp == l | pp == r){
		return;
	}
	cost += (p[r] - p[l]);
	f(l, pp);
	f(pp,r);
}

signed main(){
	int n, L;
	cin >> n >> L;
	p[0] = 0;
	for(int i = 1; i <= n; i++){
		cin >> p[i];
	}
	p[n+1]=L;
	f(0, n+1);
	
	cout << cost << '\n'; 
}

P-1-7

https://zerojudge.cchs.chc.edu.tw/Submissions



























#include<bits/stdc++.h>
using namespace std;
int c;
int n;
int arr[30];
void f(int x, int i){
	if(i >= n){
		if(x % 10009 == 1){
			//cout << x <<'\n'; 
			c++;
		}
		return;
	}
	f((x * arr[i])%10009, i+1);
	f(x,i+1);
}
int main(){
	cin >> n;
	
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	
	f(1, 0);
	cout << c - 1<< '\n';
}

P-2-2

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a140




























#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin >> n;
	int arr[n];
	int sarr[n];
	for(int i = 0; i < n; i++){
		cin >> arr[i];
		sarr[i] = arr[i];
	}
	sort(sarr, sarr+n);
	int change[n];
	change[0] = sarr[0];
	int num = 1;
	for(int i = 1; i < n; i++){
		if(sarr[i] != sarr[i-1]){
			change[num++] = sarr[i];
		}
	}
	for(int i = 0; i < n; i++){
		arr[i] = lower_bound(change, change+num, arr[i]) - change;
	}
	for(int i = 0 ;i < n; i++){
		cout << arr[i] << ' '; 
	}cout << '\n';
}

P-2-3

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a141























#include<bits/stdc++.h>
using namespace std;
#define int long long
int p;
int pow_(int x, int y){
	int r = 1;
	if(y == 0)return 1;
	int a = x;
	while(y > 0){
		if(y & 1){
			r = (r * a) % p;	
		}
		a = (a * a) % p;
		y >>= 1;
	}
	return r;
}
signed main(){
	int x, y;
	cin >> x >> y >> p;
	cout << pow_(x,y) << '\n';
}

P-2-6

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a155




























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

signed main(){
	int m ,n , k;
	while(cin >> m >> n >> k){
		int A[m];
		set<int> st;
		for(int i = 0; i < m; i++){
			cin >> A[i];
		}
		for(int i = 0; i < n; i++){
			int tmp;
			cin >> tmp;
			st.insert(tmp);
		}
		int count_ = 0;
		for(int i = 0; i < m; i++){
			auto b = st.find(k - A[i]);
			if(b != st.end()){
				count_++;
			}
		}
		cout << count_ << '\n';
	}	
}

P-2-11

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a162




























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

signed main(){
	int n, k;
	cin >> n >> k;
	int A[n];
	for(int i = 0; i < n; i++){
		cin >> A[i];
	}
	set<int> pre;
	pre.insert(0);
	int pre_sum = 0;
	int closest_sum = INT_MIN;
	for(int i = 0; i < n; i++){
		pre_sum += A[i];
		//k >= pre_sum - x  ->  x >= pre_sum - k
		auto it = pre.lower_bound(pre_sum - k);
		if(it != pre.end()){
			closest_sum = max(closest_sum , pre_sum - *it);
		}
		pre.insert(pre_sum);
	}
	
	cout << closest_sum << '\n'; 
}

P-3-2

https://zerojudge.cchs.chc.edu.tw/Submissions



























































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

bool f(char a, char b){
	if(a == '(' and b == ')'){
		return 1;
	}
	else if(a == '[' and b == ']'){
		return 1;
	}
	else if(a == '{' and b == '}'){
		return 1;
	} 
	else{
		return 0;
	}
}

void check(stack<char> &st){
	if(st.size() < 2){
		return;
	}
	char b = st.top();
	st.pop();
	char a = st.top();
	st.pop();
//	cout << a << ' '<< b << '\n';
	bool flag = f(a, b);
//	cout << flag << '\n';
	if(flag){
		check(st);
	}
	else{
		st.push(a);
		st.push(b);
		return;
	}
	
}

int main(){
	string s;
	while(cin >> s){
		stack<char> st;
		st.push(s[0]);
		for(int i = 1; i < s.size(); i++){
			st.push(s[i]);
			check(st);
			
		}
		if(st.size() == 0){
			cout << "yes" << '\n';
		}
		else{
			cout << "no" << '\n';
		}
	}	
}

P-3-4

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a167






























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

int update(vector<pair<int,int> > &st, int h){
	while(h >= st[st.size()-1].first){
		auto it = st.end();
		it = prev(it);
		st.erase(it);
	}
	return st[st.size()-1].second;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n;
	cin >> n;
	vector<pair<int,int> > st;

	st.push_back(make_pair(INT_MAX, 0));

	int ans = 0;
	for(int i = 1 ; i <= n; i++){
		int h;
		cin >> h;
		ans += i - update(st,h);
		st.push_back(make_pair(h,i));
	}
	cout << ans << '\n';
}

P-3-6

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a173







































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

int main(){
	int n, l;
	cin >> n >> l;
	map<int,int> mp;
	int c[n];
	int h[n];
	for(int i = 0; i <n; i++){
		cin >> c[i];
	} 
	for(int i = 0; i < n; i++){
		cin >> h[i];
	}
	mp[0] = INT_MAX;
	mp[l] = INT_MAX;
	for(int i = 0; i < n; i++){
		mp[c[i]] = h[i]; 
	} 
	int count_ = 0;
	int highest = 0;
	for(auto it = next(mp.begin()); it != prev(mp.end());){
//		cout << it -> first << ' ' << it->second << '\n';
		if(it -> first - it -> second >= prev(it) -> first or it -> first + it -> second <= next(it) -> first){
//			cout <<"::"<< it -> first << ' ' << it->second << '\n';
			count_++;
			highest = max(highest, it -> second);
			auto tmp = prev(it);
			mp.erase(it);
			it = tmp;
		}
		else{
			it++;
		}
	}
	cout << count_ << '\n' << highest << '\n';
}

P-3-7

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a174




































#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int n, k;
	cin >> n >> k;
	deque<int> dq;
	int arr[n];
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	int sum = 0;
	int count_ = 0;
	int max_sum = 0;
	for(int i = 0; i < n; i++){
		dq.push_front(arr[i]);
		sum += arr[i];
//		cout << sum << '\n';
		while(sum > k){
			sum -= dq.back();
			dq.pop_back();
//			cout << sum << '\n';
		}
		if(sum == max_sum){
			count_++;
			
		}
		else if(sum > max_sum){
			count_ = 1;
			max_sum = sum;
		}
	}
	cout << max_sum << '\n';
	cout << count_ << '\n'; 
}

P-3-8

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a175








































#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n, k;
	cin >> n >> k;
	deque<int> dq;
	int arr[n];
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}

	int max_gap = 0;
	int maxx = INT_MIN;
	int minn = INT_MAX;
	map<int,int> mp;
	for(int i = 0; i < n; i++){
		dq.push_front(arr[i]);
		maxx = max(maxx, arr[i]);
		minn = min(minn, arr[i]);
		mp[arr[i]] += 1;
		if(i >= k){
			int tmp = dq.back();
			dq.pop_back();
			if(mp[tmp] == 1){
				mp.erase(tmp);
			}
			else{
				mp[tmp] -= 1;
			}
		}
		int minp = mp.begin() -> first;
		int maxp = next(mp.end()) -> first;
		max_gap = max(max_gap, maxp - minp);
	}
	cout << max_gap << '\n';
 
}

P-3-9

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a176































#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	map<int,int> mp;
	deque<int> dq;
	int n, l;
	cin >> n >> l;
	int maxx = INT_MIN;
	for(int i = 0; i < n ;i++){
		int a;
		cin >> a;
		dq.push_front(a);
		mp[a] += 1;
		if(i >= l){
			int tmp = dq.back();
			dq.pop_back();
			if(mp[tmp] > 1){
				mp[tmp] -= 1;
			}
			else{
				mp.erase(tmp);
			}
		}
		int s = mp.size();
		maxx = max(maxx, s );
	} 
	cout << maxx << '\n'; 
 
}

P-3-10

https://zerojudge.cchs.chc.edu.tw/Submissions































#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	deque<int> dq;
	map<int,int> mp;
	int n;
	cin >> n;
	int arr[n];
	map<int,int> count_;
	for(int i = 0; i < n; i++){
		cin >> arr[i];
		count_[arr[i]] += 1;
	}
	int total_color = count_.size(); 
	int minn = INT_MAX;
	for(int i = 0; i < n; i++){
		dq.push_front(arr[i]);
		mp[arr[i]] += 1;
		while(mp[dq.back()] > 1){
			mp[dq.back()] -= 1;
			dq.pop_back();
		}
		if(mp.size() == total_color){
			int s = dq.size();
			minn = min(minn, s);
		}
	}
	cout << minn << '\n'; 
}

P-4-1

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a310




















#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int m;
	cin >> m;
	while(m--){
		int a;cin >> a;
		int count_ = 0;
		count_ += a / 50;
		a = a % 50;
		count_ += a / 10;
		a = a % 10;
		count_ += a / 5;
		a = a % 5;
		count_ += a;
		cout << count_ << '\n';
	}
}

P-4-2

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a312



























#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int n; cin >> n;
	vector<int> enemy(n);
	int ally[n];
	for(int i = 0; i < n;i ++){
		cin >> enemy[i];
	}	
	for(int i = 0; i < n; i++){
		cin >> ally[i];
	}
	sort(enemy.begin(), enemy.end());
	sort(ally , ally +n);
	int ans = 0;
	for(int i = n-1; i >= 0 ;i--){
		auto it = lower_bound(enemy.begin(),enemy.end(),ally[i]);
		if(it != enemy.begin()){
			it = prev(it);
			ans += 1;
			enemy.erase(it);
		}
	}
	cout << ans << '\n';
}

P-4-3

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a313



















#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int n; cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	sort(arr,arr+n);
	int ans = 0;
	int sum = 0;
	for(int i = 0; i < n; i++){
		sum += arr[i];
		ans += sum;
	} 
	cout << ans << '\n';
}

P-4-4

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a314

























#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int n; cin >> n;
	vector<pair<int,int> > vc(n);
	for(int i = 0; i < n; i++){
		cin >> vc[i].second; // start
		cin >> vc[i].first; // end
	}
	sort(vc.begin(),vc.end());
	int ans = 1;
	int back_p = vc[0].first;
	for(int i = 1; i < n; i++){
		if(vc[i].second <= back_p){

		}
		else{
			ans ++;
			back_p = vc[i].first;
		}
	}
	cout << ans << '\n';
}

P-4-5

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a315

































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

struct cmp{
	bool operator()(pair<int,int> a, pair<int,int> b){ 
		double aa = (double)a.second / (double)a.first;
		double bb = (double)b.second / (double)b.first;
//		cout << "cmp "<< aa << ' ' << bb << '\n';
		return aa > bb;
	}
};
signed main(){
	int n; cin >> n;
	vector<pair<int, int> > vc(n);
	for(int i = 0; i < n; i++){
		cin >> vc[i].first;//time
	}
	for(int i = 0; i < n; i++){
		cin >> vc[i].second;//weight
	}
	sort(vc.begin(),vc.end(),cmp());
	int sum = 0;
	int ans = 0;
	for(int i = 0 ;i < n ;i++){
//		cout << vc[i].first << ' ' << vc[i].second << '\n';
		sum += vc[i].first;
		ans += sum * vc[i].second;
	}
	
	cout << ans << '\n';
}

P-4-7

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a324




































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

struct cmp{
	int num;
	bool operator<(const cmp &a)const{
		return a.num < this->num;
	}
};

signed main(){
	int n;cin >> n;
	priority_queue<cmp> pq;
	for(int i = 0; i < n; i++){
		int a;cin >> a;
		cmp c;
		c.num = a;
		pq.push(c);
	}
	
	int sum = 0;
	while(pq.size() > 1){
		int a = pq.top().num;
		pq.pop();
		int b = pq.top().num;
		pq.pop();
		sum += a + b;
		cmp c;
		c.num = a + b;
		pq.push(c);
	}
	cout << pq.top().num << '\n';
	cout << sum << '\n';
} 



























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


signed main(){
	int n;cin >> n;
	priority_queue<int ,vector<int>, greater<int> > pq;
    #priority_queue<int ,deque<int>, greater<int> > pq;
	for(int i = 0; i < n; i++){
		int a;cin >> a;
		pq.push(a);
	}
	
	int sum = 0;
	while(pq.size() > 1){
		int a = pq.top();
		pq.pop();
		int b = pq.top();
		pq.pop();
		sum += a + b;
		pq.push(a + b);
	}
	cout << pq.top() << '\n';
	cout << sum << '\n';
}

P-4-10

https://zerojudge.cchs.chc.edu.tw/Submissions











































#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
int p[100005];
bool play(int f){
	int now = f;
	int c = 0;
	for(int i = 0; i < n; i++){
		if(p[i] > f){
			return 0;
		}
		else if(p[i] > now){
			c++;
			now = f - p[i];
		}
		else{
			now -= p[i];
		}

		if(c > m){
			return 0;
		}
	}
	return 1;
}
signed main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> p[i];
	}

	int f = 0;
	for(int j = (1e18 - f) / 2; j > 0; j >>= 1){
		while(play(f+j) == 0){
			f += j;
		}
	}
	f += 1;
	cout << f << '\n';
}

P-4-11

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a326

解法1






































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

signed main(){
	int n;
	cin >> n;
	vector<pair<int,int>> vc;
	for(int i = 0; i < 2*n; i++){
		int x;
		cin >> x;
		vc.push_back({x,i % 2});
	}
	sort(vc.begin(), vc.end());
	auto start = vc.begin();
	int previous_state;
	int state = 1;
	int ans = 0;
	for(auto it = next(vc.begin()); it != vc.end(); it++){
		if(it -> second == 1){
			previous_state = state;
			state--;
		}
		else{
			previous_state = state;
			state++;
		}
		if(state == 0 and previous_state > 0){
			ans += it -> first - start -> first;
		}
		else if(state == 1 and previous_state == 0){
			start = it;
		}
	}
	cout << ans << '\n';
}

解法2




























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

signed main(){
	int n;
	cin >> n;
	vector<pair<int,int> > vc;
	for(int i = 0 ;i < n; i++){
		int l, r;
		cin >> l >> r;
		vc.push_back({l,r});
	}
	sort(vc.begin(),vc.end());
	int total = 0;
	pair<int,int> last = vc[0];
	for(int i = 1; i < n; i++){
		if(vc[i].first > last.second){
			total += last.second - last.first;
			last = vc[i];
		}
		last.second = max(last.second, vc[i].second);
	}
	total += last.second - last.first;
	cout << total << '\n';
}

P-4-15

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a327

解法1:掃描線




























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

int dis(pair<int,int> a, pair<int,int> b){
	return abs(a.first - b.first) + abs(a.second - b.second);
}

signed main(){
	int n;
	cin >> n;
	vector<pair<int,int> > vc;
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		vc.push_back({x,y});
	}
	sort(vc.begin(),vc.end());
	int d = INT_MAX;
	for(int i = 0; i < n-1; i++){
		for(int j = i+1; j < n; j++){
			if(abs(vc[i].first - vc[j].first) > d)break;
			d = min(d, dis(vc[i], vc[j]));
		}
	}
	cout << d << '\n'; 
}

解法二:掃描線+set二分搜





































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

int dis(pair<int,int> a, pair<int,int> b){
	return abs(a.first - b.first) + abs(a.second - b.second);
}

signed main(){
	int n;
	cin >> n;
	vector<pair<int,int> > vc;
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		vc.push_back({x,y});
	}
	sort(vc.begin(),vc.end());
	set<pair<int,int> > st;
	st.insert({vc[0].second,vc[0].first});
	int d = INT_MAX;

    for(int i = 1, l = 0; i < n;i++){
        while(l < i && (vc[i].first - vc[l].first) > d){
            st.erase({vc[l].second,vc[l].first});
            l++;
        }
		auto itdown = st.lower_bound({vc[i].second - d, 0});
		auto itup = st.upper_bound({vc[i].second + d, 0});
		for(auto it = itdown; it != itup; it++){
			d = min(d, dis(vc[i], {it->second,it->first}) );
		}
		st.insert({vc[i].second, vc[i].first});
	}
	cout << d << '\n'; 
}

解法3:分治




















































#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
vector<pair<int,int> > vc;

int dis(pair<int,int> a, pair<int,int> b){
	return abs(a.first - b.first) + abs(a.second - b.second);
}

bool cmp(pair<int,int> a, pair<int,int> b){
	return a.second < b.second;
}

#define m (l+r)/2
int cqd(int l, int r){
	if(r - l == 1){
		return INT_MAX;
	}
	int ld = cqd(l,m);
	int rd = cqd(m,r);
	int d = min(ld, rd);
	vector<pair<int,int> > tmp;
	for(int i = l; i < r; i++){
		if((vc[i].first - vc[m].first)*(vc[i].first - vc[m].first) < d){
			tmp.push_back(vc[i]);
		}
	}
	sort(tmp.begin(),tmp.end(),cmp);
	for(int i = 0 ; i < tmp.size() ;i++){
		for(int j = i + 1; j < tmp.size(); j++){
			if((tmp[i].second - tmp[j].second)*(tmp[i].second - tmp[j].second) > d){
				break;
			}
			d = min(d, dis(tmp[i], tmp[j]));
		}
	}
	
	return d;
}

signed main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		int x,y;
		cin >> x >> y;
		vc.push_back({x,y});
	}
	sort(vc.begin(),vc.end());
	cout << cqd(0,n) << '\n';
}

P-5-4

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a333











































#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[100005];
#define m (l+r)/2
int dc(int l, int r){
	if(r - l == 1){
		return 0;
	}

	int c = 0;
	c += dc(l, m);
	c += dc(m, r);

	vector<int> tmp;
	for(int i = m; i < r; i++){
		tmp.push_back(a[i]);
	}
	tmp.push_back(INT_MAX);
	sort(tmp.begin(), tmp.end());
	for(int i = l; i < m; i++){
		auto it = lower_bound(tmp.begin(),tmp.end(),a[i]);
		
		if(it != tmp.end()){
			c += it - tmp.begin();

		}
		
	}
	return c;
}

signed main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	cout << dc(0, n) << '\n';
	return 0;
}

P-6-1

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a335

bottom-up






















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

int n;
int a[100005];
int dp[100005];

signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	dp[1] = a[1];
	dp[2] = a[2];
	for(int i = 3; i <= n; i++){
		dp[i] = a[i] + min(dp[i-1], dp[i-2]);
	}
	cout << dp[n] << '\n';
}

top-down




































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

int p[100005];
int dp[100005]={-1};
int f(int x){
	int a, b;
	if(dp[x-1] > 0){
		a = dp[x-1];
	}
	else{
		a = f(x-1);
		dp[x-1] = a;
	}
	if(dp[x-2] > 0){
		b = dp[x-2];
	}
	else{
		b = f(x - 2);
		dp[x-2] = b;
	}
	return p[x] + min(a, b);
	
}
signed main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> p[i];
	}
	dp[0] = p[0];
	dp[1] = p[1];
	cout << f(n-1) << '\n';
}

P-6-2

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a336

























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

int n;
int a[100005];
int dp[100005];

signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	dp[0] = 0;
	dp[1] = a[1];
	dp[2] = max(a[2], a[1]);

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

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

p-6-3

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a337























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

int n;
int a[100005];
int dp[100005];

signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	dp[0] = INT_MAX;
	dp[1] = a[1];
	dp[2] = a[2];
	for(int i = 3; i <= n; i++){
		dp[i] = a[i] + min(dp[i-3], min(dp[i-2], dp[i-1]));
	}
	cout << min(dp[n], dp[n-1]) << '\n';
}

p-6-6

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a340


































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

signed main(){
	int n ,m; cin >> n >> m;
	int a[n][m];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}
	int dp[n][m];
	dp[0][0] = a[0][0];
	for(int i = 1; i < n; i++){
		dp[i][0] = dp[i-1][0] + a[i][0];
	}
	for(int i = 1; i < m; i++){
		dp[0][i] = dp[0][i-1] + a[0][i];
	}
	for(int i = 1; i < n; i++){
		for(int j = 1; j < m; j++){
			dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
		}
	}
	// for(int i = 0; i < n; i++){
	// 	for(int j = 0; j < m; j++){
	// 		cout << dp[i][j] << ' ';
	// 	}cout << '\n';
	// }
	cout << dp[n-1][m-1] << '\n';
}

p-6-7

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a341






























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

signed main(){
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.size();
	int m = s2.size();
	int dp[n+1][m+1];
	for(int i = 0; i <= n; i++){
		dp[i][0] = 0;
	}
	for(int i = 0; i <= m; i++){
		dp[0][i] = 0;
	}
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			if(s1[j-1] == s2[i-1]){
				dp[j][i] = dp[j-1][i-1] + 1;
			}
			else{
				dp[j][i] = max(dp[j-1][i], dp[j][i-1]);
			}
		}
	}
	cout << dp[n][m] << '\n';
}

滾動





























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

signed main(){
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.size();
	int m = s2.size();
	int dp[n+1][2];
	for(int i = 0; i <= n; i++){
		dp[i][0] = 0;
		dp[i][1] = 0;
	}
	int from = 0, to = 1;
	for(int i = 1; i <= m; i++){
		for(int j = 1; j <= n; j++){
			if(s1[j-1] == s2[i-1]){
				dp[j][to] = dp[j-1][from] + 1;
			}
			else{
				dp[j][to] = max(dp[j-1][to], dp[j][from]);
			}
		}
		swap(from, to);
	}
	cout << dp[n][from] << '\n';
}

p-6-8

global alignment

先把子問題寫出來









































#include <bits/stdc++.h>
using namespace std;
#define int long long
int val(char a, char b){
    if(a == b){
        return 8;
    }
    else if(a == '-' or b == '-'){
        return -3;
    }
    else{
        return -5;
    }
}
signed main(){
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.size();
	int m = s2.size();
	int dp[n+1][m+1];
	for(int i = 0; i <= n; i++){
		dp[i][0] = i * -3;
	}
	for(int i = 0; i <= m; i++){
		dp[0][i] = i * -3;
	}
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = max(dp[i-1][j-1] + val(s1[i-1], s2[j-1]),
                           max(dp[i-1][j] + val(s1[i-1], '-'),
                               dp[i][j-1] + val('-', s2[j-1])));
        }
    }
    for(int i = 0; i <= n; i++){
        for(int j  = 0; j <= n; j++){
            cout << dp[i][j] << ' ';
        }cout << '\n';
    }
	cout << dp[n][m] << '\n';
}

local alignment












































#include <bits/stdc++.h>
using namespace std;
#define int long long
int val(char a, char b){
    if(a == b){
        return 8;
    }
    else if(a == '-' or b == '-'){
        return -3;
    }
    else{
        return -5;
    }
}
signed main(){
	string s1, s2;
	cin >> s1 >> s2;
	int n = s1.size();
	int m = s2.size();
	int dp[n+1][m+1];
	for(int i = 0; i <= n; i++){
		dp[i][0] = 0;
	}
	for(int i = 0; i <= m; i++){
		dp[0][i] = 0;
	}
    int max_score = INT_MIN;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            dp[i][j] = max(val(s1[i-1], s2[j-1]),
                       max(dp[i-1][j-1] + val(s1[i-1], s2[j-1]),
                       max(dp[i-1][j] + val(s1[i-1], '-'),
                           dp[i][j-1] + val('-', s2[j-1]))));
            max_score = max(max_score, dp[i][j]);
        }
    }
    // for(int i = 0; i <= n; i++){
    //     for(int j  = 0; j <= n; j++){
    //         cout << dp[i][j] << ' ';
    //     }cout << '\n';
    // }
	cout << max_score << '\n';
}

這題懶得寫滾動DP了

p-6-9

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a343


























#include<bits/stdc++.h>
using namespace std;
// #define int long long
int dp[101][100005];
int w[101];
int val[101];
signed main(){
    int  n, W;
    cin >> n >> W;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> val[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < w[i]; j++){
            dp[i][j] = dp[i-1][j];
        }
        for(int j = w[i]; j <= W; j++){
            dp[i][j] = max(dp[i-1][j], val[i] + dp[i-1][j - w[i]]);
        }
    }
    cout << dp[n][W] << '\n';
}

滾動寫法(一維)

從後到前























#include<bits/stdc++.h>
using namespace std;
// #define int long long
int dp[100005];
int w[101];
int val[101];
signed main(){
    int  n, W;
    cin >> n >> W;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> val[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = W; j >= w[i]; j--){
            dp[j] = max(dp[j], val[i] + dp[j - w[i]]);
        }
    }
    cout << dp[W] << '\n';
}

P-6-10

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a344























#include<bits/stdc++.h>
using namespace std;
// #define int long long
int dp[100005];
int w[101];
int val[101];
signed main(){
    int  n, W, S;
    cin >> n >> W >> S;
    int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        sum += w[i];
    }

    for(int i = 1; i <= n; i++){
        for(int j = W - S; j >= w[i]; j--){
            dp[j] = max(dp[j], w[i] + dp[j - w[i]]);
        }
    }
    cout << max(0,sum - dp[W - S]) << '\n';
}

p-6-11

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a345




















#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000009
int dp[101];

signed main(){
    int n;
    cin >> n;
    dp[0] = 1;
    dp[1] = 1;

    for(int i = 2; i <= n; i++){
        for(int j = 0; j < n; j++){
            dp[i] = (dp[i] + ((dp[j] % mod ) * (dp[i - 1 - j] % mod)) % mod) % mod;
        }
    }
    cout << dp[n] << '\n';
}

p-6-13

p-6-15

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a349

二分搜






















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


int main(){
    int n;
    cin >> n;
    vector<int> vc;
    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        auto it = lower_bound(vc.begin(),vc.end(),x);
        if(it == vc.end()){
            vc.push_back(x);
        }
        else{
            *it = x;
        }
    }
    cout << vc.size() << '\n';
}

p-6-17

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a351
































#include<bits/stdc++.h>
using namespace std;
int p[202];
int dp[202][202];
int f(int l, int r){
    if(r - l == 1){
        return 0;
    }
    if(dp[l][r] != 0){
        return dp[l][r];
    }
    else{
        int minn = INT_MAX;
        for(int i = l+1; i < r; i++){
            minn = min(minn, f(l, i) + f(i, r));
        }
        dp[l][r] = minn + (p[r] - p[l]);
        return dp[l][r];
    }
}

int main(){
    int n, L;
    cin >> n >> L;
    p[0] = 0;
    p[n+1] = L;
    for(int i = 1; i <= n; i++){
        cin >> p[i];
    }
    cout << f(0, n+1) << '\n';
}

p-7-1

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a358

鄰接矩陣





































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

int g[101][101];
int vis[101];
int main(){
    int n, m;
    cin >> n >> m;
    int s; cin >> s;
    for(int i = 0; i < m ;i++){
        int x, y;
        cin >> x >> y;
        g[x][y] = 1;
    }
    int sum = 0;
    int num = 0;
    int step = 1;
    vis[s] = 1;
    queue<pair<int,int> > q;
    q.push({s,0});
    while(q.size()){
        int now = q.front().first;
        int depth =q.front().second;
        q.pop();
        for(int i = 0; i < n; i++){
            if(g[now][i] == 1  and vis[i] == 0){
                q.push({i, depth + 1});
                vis[i] = 1;
                num += 1;
                sum += depth + 1;
            }
        }

    }
    cout << num << '\n' <<sum << '\n';
}

鄰接串列





































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

vector<int> g[101];
int vis[101];
int main(){
    int n, m;
    cin >> n >> m;
    int s; cin >> s;
    for(int i = 0; i < m ;i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
    }
    int sum = 0;
    int num = 0;
    int step = 1;
    vis[s] = 1;
    queue<pair<int,int> > q;
    q.push({s,0});
    while(q.size()){
        int now = q.front().first;
        int depth =q.front().second;
        q.pop();
        for(int i : g[now]){
            if(vis[i] == 0){
                q.push({i, depth + 1});
                vis[i] = 1;
                num += 1;
                sum += depth + 1;
            }
        }

    }
    cout << num << '\n' <<sum << '\n';
}

P-7-2

https://zerojudge.cchs.chc.edu.tw/ShowProblem?problemid=a359




































#include<bits/stdc++.h>
using namespace std;
int val[50005];
vector<int> g[50005];
int vis[50005];
int DFS(int now){
    vis[now] = 1;
    int r = val[now];
    for(int i : g[now]){
        if(vis[i] == 0){
            r += DFS(i);

        }
    }
    return r;
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> val[i];
    }
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
        if(vis[i] == 0)
            ans = max(ans, DFS(i));
    }
    cout << ans <<'\n';
}

ZeroJudge：f167. m4a1-社團 Club

https://zerojudge.tw/ShowProblem?problemid=f167
topological sort












































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

vector<int> g[1005];
int in[1005];

signed main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        in[y] ++;
    }
    queue<int> qu;
    int st;
    vector<int> seque;
    for(int i = 1; i <= n; i++){
        if(in[i] == 0)qu.push(i);
    }
    while(!qu.empty()){
        int now = qu.front();
        qu.pop();
        seque.push_back(now);
        for(int i : g[now]){
            in[i]--;
            if(in[i] == 0){
                qu.push(i);
            }
        }
    }
    if(seque.size() == n){
        cout << "YES" << '\n';
        for(int i = 0; i < n; i++){
            cout << seque[i] << '\n';
        }
    }
    else{
        cout << "NO" << '\n';
    }
}

TIOJ 1092. A.跳格子遊戲

https://tioj.ck.tp.edu.tw/problems/1092
topological sort
















































#include<bits/stdc++.h>
using namespace std;
vector<int> g[10005];
int out[10005];
int win[10005];
int main(){
    int n, e;
    while(cin >> n >> e){
        if(n == 0 and e == 0){break;} 
        for(int i = 0; i < n; i++){
            g[i].clear();
        }
        memset(out,0,sizeof(out));
        memset(win,0,sizeof(win));
        
        for(int i = 0; i < e; i++){
            int x, y; cin >> x >> y;
            g[y].push_back(x);
            out[x]++;
        }
        string s;
        cin >> s;
        queue<int> topo;//0 win  1 lose
        topo.push(n);
        win[n] = 0;
        while(!topo.empty()){
            int now = topo.front();
            topo.pop();
            for(int i : g[now]){
                out[i]--;
                if(out[i] == 0){
                    topo.push(i);
                }
                if(win[now] == 0){
                    win [i] = 1;
                }
            }
        }

         if (win[1] == 0) {
            cout << (s == "Mimi" ? "Mimi" : "Moumou") << '\n';
        } else {
            cout << (s == "Mimi" ? "Moumou" : "Mimi") << '\n';
        }
    }
    
}

1290 . F.不定向邊

https://tioj.ck.tp.edu.tw/problems/1290

































































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

struct node
{
    int val;
    int to;
    /* data */
};
vector<node> g[1005];
int used[1005];
int cost[1005];
int main(){
    int n, m;
    while(cin >> n >> m){

        int st, ed;
        cin >> st >> ed;
        for(int i = 0; i < 1005; i++){
            g[i].clear();
            cost[i] = INT_MAX;
            used[i] = 0;
        }
        
        for(int i = 0; i < m; i++){
            int a, b ,c;
            cin >> a >> b >> c;
            node tmp;
            tmp.val = c;
            tmp.to = b;
            g[a].push_back(tmp);
            tmp.to = a;
            g[b].push_back(tmp);
        }

        

        cost[st] = 0;

        priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>>> pq;
        pq.push({0, st});
        while(!pq.empty()){
            int now = pq.top().second;
            pq.pop();

            if(used[now] == 1) continue;
            used[now] = 1;
            for(auto i : g[now]){
                if(cost[now] + i.val < cost[i.to]){
                    cost[i.to] = cost[now] + i.val;
                    pq.push({cost[i.to], i.to});
                }
                
            }
        }

        if(cost[ed] == INT_MAX){
            cout << "He is very hot" << '\n';
        }
        else{
            cout << cost[ed] << '\n';
        }
    }
}

UVa 10986 Sending email

https://vjudge.net/problem/UVA-10986





























































#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
    int val;
    int to;
};
vector<node> g[20000];
int cost[20000];
int used[20000];
signed main(){
    int t;
    cin >> t;
    for(int u = 1; u <= t; u++){
        int n, m, st, ed;
        cin >> n >> m >> st >> ed;
        for(int i = 0; i < 20000; i++){
            g[i].clear();
            cost[i] = INT_MAX;
            used[i] = 0;
        }
        for(int i = 0; i < m; i++){
            int x, y, z;
            cin >> x >> y >> z;
            node tmp;
            tmp.to = y;
            tmp.val = z;
            g[x].push_back(tmp);
            tmp.to = x;
            g[y].push_back(tmp);
        }
        

        priority_queue<pair<int,int> ,vector<pair<int,int>> , greater<pair<int,int>>> pq;
        pq.push({0,st});
        cost[st] = 0;
        while(!pq.empty()){
            int now = pq.top().second;
            pq.pop();
            if(used[now] == 1){continue;}
            used[now] = 1;

            for(auto i : g[now]){
                // cout << i.val << ' ' << cost[now] << ' ' << cost[i.to] << '\n';
                if(i.val + cost[now] < cost[i.to]){
                    cost[i.to] = i.val + cost[now];
                    pq.push({cost[i.to], i.to});
                }
            }
        }
        cout << "Case #"<<u<<": ";
        if(cost[ed] == INT_MAX){
            cout << "unreachable" << '\n';
        }
        else{
            cout << cost[ed] << '\n';
        }
    }

}

UVA 11015 - 05-2 RENDEZVOUS

https://vjudge.net/problem/UVA-11015
Floyd-Warshall

























































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

signed main(){
    int n, m;
    int c = 0;
    while(cin >> n >> m){
        if(n == 0)break;
        c++;
        string s[n+1];
        vector<vector<int> > g(25,vector<int> (25));
        for(int i = 1; i <= n; i++){
            cin >> s[i];
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) g[i][j] = 0;
                else{
                    g[i][j] = INT_MAX;
                }
            }
        }
        for(int i = 0; i < m; i++){
            int a, b, c;
            cin >> a >> b >> c;
            g[a][b] = c;
            g[b][a] = c;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    if (g[i][k] != INT_MAX && g[k][j] != INT_MAX) {
                        g[j][k] = min(g[j][k], g[j][i] + g[i][k]);
                    }
                }
            }
        }


        string ans;
        int minn = INT_MAX;
        for(int i = 1; i <= n; i++){
            int tmp = 0;
            for(int j = 1; j <= n; j++){
                tmp += g[i][j];
            }
            if(tmp < minn){
                minn = tmp;
                ans = s[i];
            }
        }
        cout << "Case #"<<c<<" : "<<ans << '\n';
    }
}

UVa 558 - Wormholes

https://vjudge.net/problem/UVA-558
SPFA負環判斷























































#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
struct node{
    int val;
    int to;
};
vector<node> g[1005];
int dis[1005];
int inq[1005];
int times[1005];
int spfa(){
    queue<int> q;
    for(int i = 0; i <= n; i++){dis[i] = INT_MAX; inq[i] = 0; times[i] = 0;}
    dis[0] = 0;
    inq[0] = 1;
    q.push(0);
    while(!q.empty()){
        int now = q.front();
        inq[now] = 0;
        times[now]++;
        if(times[now] > n) return true;
        q.pop();
        for(auto i : g[now]){
            if(dis[now] != INT_MAX and dis[now] + i.val < dis[i.to]){//前面那個應該可以不用
                dis[i.to] = dis[now] + i.val;
                if(inq[i.to] == 0){
                    inq[i.to] = 1;
                    q.push(i.to);
                }
            }
            
        }
    }
    return false;
}

signed main(){
    int c;
    cin >> c;
    while(c--){
        cin >> n >> m;
        for(int i = 0; i <= n; i++)g[i].clear();
        for(int i = 0; i < m; i++){
            int x, y, t;
            cin >> x >> y >> t;
            node tmp; tmp.to = y; tmp.val = t;
            g[x].push_back(tmp);
        }
        if(spfa()) cout << "possible\n";
        else cout << "not possible\n";
    }
}

NEOJ 48 二元搜尋樹

BST 前序轉後續


























































#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
	int val;
	node* lc;
	node* rc;
	node(int x){
		val = x;lc = nullptr; rc = nullptr;
	}
};

void bst_insert(node *root, int x){
	if(x <= root->val){
		if(root->lc == nullptr){
			node *tmp = new node(x);
			root->lc = tmp;
		}
		else{
			bst_insert(root->lc, x);
		}
	}
	else{
		if(root->rc == nullptr){
			node *tmp = new node(x);
			root->rc = tmp;
		}
		else{
			bst_insert(root->rc, x);
		}
	}
}
void postorder(node *root){
	if(root->lc != nullptr){
		postorder(root->lc);		
	}
	if(root->rc != nullptr){
		postorder(root->rc);
	}
	cout << root->val << '\n';

}
int main(){
	cin >> n;

	int x;
	cin >> x;
    node *root = new node(x);
	for(int i = 1; i < n; i++){
		cin >> x;
		bst_insert(root, x);
	}

	postorder(root);
	
}
Last changed by 
 
samson_chaechae
熱愛程式的高中生 比較大型的東西就會放在github "https://github.com/samsonjaw" 聯絡Email "samsonjaw1226@gmail.com"
0
390

Read more

背包問題

背包問題就是一種解決，如何用有限空間取得最大價值的問題而實際概念就是用小問題計算大問題的答案，是一種DP問題

Jul 28, 2025
C++的基礎架構

編者：111年初階教學趙炫翔

Jul 20, 2025
清交APCS組/交大資安組/成大資工智慧系統組 二階心得

交大apcs/清大apcs/交大資安/成大智慧系統

May 30, 2024
選擇性敘述 if

if 顧名思義就是對條件進行判斷，如果符合判斷就執行

May 29, 2024
Read more from samson_chaechae
Published on HackMD