d904: 換零錢 解題心得

題目來源：https://zerojudge.tw/ShowProblem?problemid=d904
USACO2007January Competition

一般人拿到這題後，會不自覺地從最大的硬幣開挑選，然後順著往下挑，按這思維往下，可以順利地拿到80%的分數，但最後兩題測資不會對，給一個測資讓大家參考：
93 5
60
31
5
2
1
在上面這組測資，如果先拿60，那麼最佳狀況為60+31+1+1，但如果先拿31則最佳狀況為31+31+31。
所以基本上這題大方向還是要用窮舉演算法，那麼我的選擇是DFS，當然過程中要做一些剪枝的動作來加速運算時間。
以下附上C++跟PYTHON的程式碼，有任何疑問都歡迎找我討論。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
vector<int> v;
int n, m;
int minCount = 9999;

void dfs(int i, int count, int sum, int totalCount) {
    if (i == v.size()) return;
    sum += v[i] * count;
    //cout <<sum;
    totalCount += count;
    if (sum > n || totalCount > minCount) return;
    if (i + 1 == v.size() - 1) {
        if ((n - sum) % v[i + 1] == 0) {
            totalCount += (n - sum) / v[i + 1];
            sum = n;
        }
        else {
            return;
        }
    }
    if (sum == n) {
        if (minCount > totalCount) {
            minCount = totalCount;
        }
        return;
    }
    if (i == v.size() - 1) return;
    for (int k = i + 1; k < v.size(); k++) {
        if (n / v[k] < 0) continue;
        for (int j = 0; j <= n / v[k]; j++) {
            if (j + totalCount > minCount) break;
            dfs(k, j, sum, totalCount);
        }
        break;
    }
}

bool comp(const int& a, const int& b)
{
    return a > b;
}

int main()
{
    cin >> n >> m;
    while (m--) {
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end(), comp);
    int count = 0;

    for (int j = n / v[0]; j >= 0; j--) {
        dfs(0, j, 0, 0);
    }
    cout << minCount;

    return 0;
}

PYTHON：

mins = 99999

def dfs(sum , index , counts , target):
  global mins , cc
  sum += coins[index]
  #print(sum)
  counts += 1
  if counts >= mins:
    return
  elif sum == target:
    if mins > counts:
      mins = counts
    return
  else:
    for i in range(index , cc):
      if sum+coins[i] > target:
        continue
      dfs(sum , i , counts , target)




a = input().split(" ")
target = int(a[0])
cc = int(a[1])
coins = []
count = 0;
#count是這條路徑取的硬幣數
for i in range(cc):
  coins.append(int(input()))
coins.sort()
coins.reverse()
sum = 0
for i in range(cc):
  if sum+coins[i] > target:
    continue
  dfs(sum , i , count , target)

print(mins)

b967: 第 4 題 血緣關係 解題心得

zerojudge題目網址：https://zerojudge.tw/ShowProblem?problemid=b967
題目來源：APCS考題
題目網址：
https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx6c2dpdGl0aXR8Z3g6NDQ4NmIyNzljY2Q2N2ZiYg

解題策略：
將這棵樹視為無向樹，從任一起點出發，找尋離自己最遠的兩個端點，且不能經過重複的點，將距離相加就是答案，例如以０為起點，０１５＋０３６或０１４＋０３６距離都是２，所以２＋２＝４，或者以１為起點出發。１４＋１０３６或１５＋１０３６距離為１＋３＝４。
為了完成上面解法，在收測資的時候需要讓每個端點都知道自己可以到哪幾個端點。

程式碼如下：
有任何問題歡迎留言或私我或是ＭＡＩＬ給我。

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> nodes;
vector<int> book;
int ans;


int dfs(int now, int last_steps) {
    book[now] = 1;
    int dis1 = 0 , dis2 = 0 , dis;
    for (int x : nodes[now]) {
        if (!book[x]) {
            dis = dfs(x, last_steps + 1) + 1;
            if (nodes[now].size() == 0) continue;
            if (dis >= dis1) {
                dis2 = dis1;
                dis1 = dis;
            }
            else if (dis > dis2) {
                dis2 = dis;
            }
        }
    }
    ans = max(max(ans, dis1 + dis2), dis1 + last_steps);
    return dis1;
}

int main() {
    cin.tie(0),cin.sync_with_stdio(false);
    int n, a, b;
    while (cin >> n) {
        ans = 0;
        nodes.clear();
        nodes.resize(n);
        book.assign(n, 0);
        for (int i = 1; i < n; i++) {
            cin >> a >> b;
            nodes[a].push_back(b);
            nodes[b].push_back(a);
        }
        dfs(0, 0);
        cout << ans << "\n";
    }
}

b006: 矩形旋轉 解題心得

題目來源：https://zerojudge.tw/ShowProblem?problemid=b006

內容

給定若干個各種長寬的矩形，請求出最多有多少個矩形可以疊在一起使得上方的矩形其長與寬均不大於下方的矩形。注意，上下矩形的邊必須平行，也就是說矩形可以 90 度旋轉或不旋轉但是不能轉其他角度。

輸入說明
每一行的第一個數字為矩形的個數 n，接著有 2n 個正整數，分別為第一個 矩形的長與寬、第二個矩形的長與寬、…。所有的數字皆以空白間格，數字不大 於 30000。例如下面範例的第一行代表有三個矩形尺寸分別為 1×5、2×3、3×2， 對於此輸入可以有兩個矩形疊在一起。

輸出說明
依序每一行輸出每一個案例所求之值。

範例輸入 #1                               範例輸出 #1
3                                                  2
1 5 2 3 3 2                                   4
5
1 1 4 8 5 6 6 7 7 7

第一、其實這題題目的測資很軟，錯的上傳也會是對的，就像我第一眼看到這程式的時候，我把它誤解成跟b966: 第 3 題 線段覆蓋長度一樣的題目了(點題目可以看到我該題的解法)，所以我用pair來裝矩形的兩邊，將長邊都放到pair的first，短邊放到second...。
附上錯誤的程式碼如下：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    while(cin >> n) {
        int m = 0;
        vector<pair<int , int>> vp;
        while(m++ < n) {
            int x , y;
            cin >> x >> y;
            pair<int , int> p;
            if(x > y) {
                p.first = x;    p.second = y;
            } else {
                p.first = y;    p.second = x;
            }
            vp.push_back(p);
            
        }
        sort(vp.begin() , vp.end());
        int count = 0;
        int max = 0;
        for(int i = n-1; i > 0 ; i--) {
            //cout << "vp[i].second = " << vp[i].second << " vp[i-1].second = " << vp[i-1].second <<" i = " << i << endl;;
            if(vp[i].second < vp[i-1].second) {
                if(max < count) max = count;
                count = 0;
            } else {
                if(count == 0) {
                    count = 2;
                } else
                    count++;
            }
        }
        if(max < count) max = count;
        cout << max <<endl;
    }

    return 0;
}

上面的程式問題在於如果面對(5 4)(4 4)(2 7)(2 1)(1 1)，程式會判定疊成兩堆分別為(5 4)(4 4)跟(2 7)(2 1)(1 1)，但其實正確答案是(5 4)(4 4)(2 1)(1 1 )。

仔細觀察測資後發現，(5 4)(4 4)(2 7)(2 1)(1 1)我們可以由小到大依序判別自己最多可以跟幾個矩形交疊。
ex.
1 1(自己跟自己玩，只能疊一個)
2 1前面只有1 1可以疊所以他可以疊1+1個(包含自己)
2 7前面有1 1 跟 2 1可以疊選擇1 1就是疊兩個選擇2 1就是疊2+1(含自己)個
4 4前面有2 7.  2 1. 1 1可以選，結論是選可惜2 7不能選，所以選2 1來疊總共疊2+1(含自己)個
5 4前面有4 4. 2 7. 2 1. 1 1可以選4 4跟2 7最有利但是2 7不能選，所以選4 4故總共3+1個

以下附上正確的程式碼：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    int n;
    int m = 0, x, y;
    int count;
    int max;
    vector<pair<int, int>> vp;
    vector<int> cuc;
    while (cin >> n) {
        m = 0;
        vp.clear();
        cuc.clear();
        while (m++ < n) {
            cin >> x >> y;
            pair<int, int> p;
            if (x > y) {
                p.first = x;    p.second = y;
            }
            else {
                p.first = y;    p.second = x;
            }
            vp.push_back(p);

        }
        sort(vp.begin(), vp.end());
        max = 1;
        for (int i = 0; i < n; i++) {
            count = 1;
            for (int j = i-1; j >= 0; j--) {
                if (vp[i].second >= vp[j].second) {
                    if (max < count + cuc[j]) {
                        max = count + cuc[j];
                    }
                }
            }
            cuc.push_back(max);
        }
        cout << max << "\n";

        
    }

    return 0;
}

b966: 第 3 題 線段覆蓋長度 解題心得

題目來源：https://zerojudge.tw/ShowProblem?problemid=b966

給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。

例如給定 4 個線段：(5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 。

這題跟某題方形覆蓋有點像，只是這題要算的是覆蓋長度，首先我們先將所有的線段根據起點由小到大排序，如此前後兩線段就只剩下三種可能。

EX：

1.(3 , 9)、(4 , 7)

2.(3 , 9)、(12 ,18)

3.(3 , 9)、(6 , 12)

只要處理好這三種情況，這題就可以迎刃而解。

以下附上程式碼，有什麼問題可以在下面留言或MAIL給我來討論囉。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	vector<pair<int, int>> vp;
	int n , m , o , q = 0 , len = 0;
	cin >> n;
	pair<int, int> p;
	while (q++ < n) {
		cin >> m >> o;
		p.first = m;
		p.second = o;
		vp.push_back(p);
	}
	sort(vp.begin(), vp.end());
	len = vp[0].second - vp[0].first;
	pair<int, int> sample = vp[0];
	for (int i = 1; i < n; i++) {
		if (vp[i].second <= sample.second) {
			continue;
		}
		else if (vp[i].first >= sample.second) {
			sample = vp[i];
			len += vp[i].second - vp[i].first;
		}
		else {
			len += vp[i].second - sample.second;
			sample.second = vp[i].second;
		}
	}
	cout << len;
}

格子遊戲

格子遊戲

透過簡單的互動式遊戲，讓孩子可以快樂的玩數學。

試著點擊左下方小蘋果，試著滿足右方的格子數字如下圖。

左下角加左上角共五顆蘋果，滿足左下角的數字要求，

右下角加右上角共五顆蘋果，滿足右下角的數字要求，

左上角加右上角共六顆蘋果，滿足右上角的數字要求，

左下角加右下角共四顆蘋果，滿足右下角的數字要求。

每次更新網頁都會是全新的題目唷，一起帶著孩子快樂玩數學吧。