演算法

程式世界

C(++)

• 資訊比賽基本上全靠它
• 古老，所以很多人用
• 低階，貼近機器
• 程式跑得快而且記憶體用的直接，但寫起來比較累

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) return false;
    }
    return true;
}
          

Python

• 個人推薦初學者語言
• 美國大學似乎越來越多？
• 高階，簡潔，配件多，有社群
• Google, NASA, NumPy, Sage...

from math import sqrt
def isPrime(n):
    if n <= 1: return False
    for p in range(2, int(sqrt(n))+1):
        if n % p == 0: return False
    return True
          

JavaScript

• 網路的語言！這個投影片背後就是它
• 雖然名字類似，但跟「Java」語言其實不像
• 設計有不少（公認為的）缺點⋯⋯例如，沒有整數，只有浮點數⋯⋯
• [1] != [1], [1] == 1!?

function isPrime(n) {
    if (n <= 1) return false;
    for (var p = 2; p * p <= n; p++) {
        if (n % p == 0) return false;
    }
    return true;
}
          

Haskell

• 個人嗜好
• 純函數式語言，充滿高等數學抽象代數(abstract algebra)跟範疇論(category theory)的東西
• 學習Haskell會強迫你重新學習如何寫程式

isPrime :: (Integral a) => a -> Bool
isPrime n
      | n <= 1 = False
      | otherwise = all ((/= 0) . (n `mod`)) $
            takeWhile ((<= n) . (^2)) [2..]
          

以上語言選擇純屬個人觀點

程式語言超級多，每個人喜好不同

• C++ ~ Java, Objective-C, C#, D, Go, Rust
• Python, JavaScript ~ Perl, PHP, Ruby, Lua
• compile to JavaScript ~ CoffeeScript, Coco, LiveScript, etc.
• Haskell ~ OCaml/SML, F#, Scala
• 還有一大群Lisp: Common Lisp, Scheme, Clojure, Racket
• 看TIOBE index（雖然它的算法也有人批評）

更別說模組了

假設你要用Python寫個網站好了

• Django?
• Pyramid?
• TurboGears?
• Zope2?
• CubicWeb?
• Flask?
• ???

還有工具⋯⋯

Vim	Git / GitHub
	©® GitHub 2014

學程式要做什麼？

• 比賽
• 寫網頁
• 寫遊戲
• 工作面試
• 協助科展
• 好玩

Piet Program Gallery

© Joshua Schulter under GPL

學演算法要做什麼？

• 比賽

當然做其他事情也需要學演算法，但更會遇到很多架構／設計的問題，或是需要學習用各種模組跟API，或是debug。

演算法是什麼？

• 有限(finite)
• 明確(definite)
• 輸入(input)(零個或更多)
• 輸出(output)
• 有效(effective)

(Knuth, The Art of Computer Programming)

演算法是什麼？

Source: Wikicommons

這是演算法嗎？

演算法是什麼？

可以解決的問題：

• GCD
• 排序：如何把一個數列重排成遞增的？
• 快速冪：如何計算bⁿ mod m?
• 質數判斷；質因數分解
  • RSA加密法就是依靠沒有快速的質因數分解演算法
• 凸包：給定一些平面上的點，如何計算它們的凸包頂點？

GCD

GCD

gcd(a, b) = ?

1. If b = 0 then gcd(a, b) = a
2. If b ≠ 0 then gcd(a, b) = gcd(b, a mod b)

「= 0」、「mod」是有限、明確、有效的。

在GCD裡面再計算一次GCD是明確、有效的（做同樣的判斷、計算，直到有答案為止）。

是有限的（為什麼？）

GCD

比賽時在幹嘛？

• 讀題目
• 寫程式
• 上傳
• 等回傳AC, WA, TLE*
• 下一題

線上賽似乎都很殘忍的只回傳部分訊息

為信仰而戰！
遍、地、開、WA！
— rilak

前提

• 宣告變數、四（五）則運算、輸入輸出
• 定義、呼叫函數／子程序
• 比較運算子
• if, while, for
• 數組(array)

學過的先做一下題目吧。例如挑戰2013 NPSC高中組決賽破台。(先做A, C, G)

宣告變數、四（五）則運算、輸入輸出

int a, b;
cin >> a >> b;
cout << a + b << endl;
cout << a - b << endl;
cout << a * b << endl;
cout << a / b << endl; // !!!
cout << a % b << endl; // mod
//   7  / 3 = ?
// (-7) / 3 = ?
// (-7) % 3 = ?
            

宣告變數、四（五）則運算、輸入輸出

int x; // -2^31 ~ 2^31 - 1（通常）
double y; // 浮點，可表示非整數。不完全精確，所以比較時請小心
// 例：abs(y - yy) < 1e-8
long long z; // -2^63 ~ 2^63 - 1（通常）

// 常需要打"long long"都會感到困擾。
typedef long long ll;
ll y;
// 請不要在競賽外這樣寫
            

定義、呼叫函數／子程序

#include <iostream>
using namespace std;
int cube(int x) {
    return x * x * x;
}
int main() {
    cout << cube(7) << endl;
}
            

順帶一提，競賽爭手速跟思考速度，在程式競賽之外寫using namespace std;其實不是好習慣

比較運算子

int a, b;
cin >> a >> b;
if (a == b) cout << "相等" << endl;
if (a != b) cout << "不相等" << endl;
if (a < b) cout << "小於" << endl;
if (a > b) cout << "大於" << endl;
if (a <= b) cout << "小於等於" << endl;
if (a >= b) cout << "大於等於" << endl;
            

單獨!就是「非」的意思，跟=結合為「不等於」很好記。（晚一點會看到）

if, while, for

#include <iostream>
void printTwoFactors(int x) {
    int c = 0;
    while (x % 2 == 0) { x /= 2; c++; } // 被執行零至多次，直到x是奇數為止
    if (c > 0) { // 執行一次，或不執行
        cout << "2^" << c << " * " << x << endl;
    } else { // if後的else可加可不加
        cout << x << endl;
    }
}
int main() {
    for (int i = 0; i < 100; i++) { // 最常用法
        printTwoFactors(i); // i會跑遍1到100
    }
}
            

數組(array)

int a0, a1, a2, a3, ..., a99;

⇒ int a[100];

a[0], a[1], a[2], ..., a[99];

#include <iostream>
int div[100];
int main() {
    for (int i = 1; i < 100; i++) {
        for (int j = i; j < 100; j += i) { // j = i, 2i, 3i...
            div[j]++;
        }
        cout << i << ": " << div[i] << endl;
    }
}
            

進階語法

初階可以先跳過；大約照重要性跟實用性遞減排序。

我寫的有點過火，不用看完

• ?:
• 邏輯運算子
• <algorithm>, <vector>
• <cstdio>

?:

可以當成一個值或算式的if/else

if (a == 1) {
    cout << b << endl;
} else {
    cout << (-b) << endl;
}
            

↕

cout << (a == 1 ? b : (-b)) << endl;
            

另外，==跟其他比較式的結果都也是數字：0（false、假）或1（true、真）

if、while、for、?:都把0當成false，≠0當成true。不過你不知道這件事寫出來的程式會比較可讀。

邏輯運算子

&&, ||, !

and, or, not

「且」、「或」、「非」

1 && 1 = 1

1 && 0 = 0 && 1 = 0 && 0 = 0

1 || 1 = 1 || 0 = 0 || 1 = 1

0 || 0 = 0

if (a == 0 || b == 0) {
    cout << "至少有一個0";
}
            

<algorithm>, <vector>

#include <algorithm>
#include <vector>
using namespace std;
int a[100];
vector<int> v;
int main() {
    for (int i = 0; i < 100; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < 100; i++) {
        int x; scanf("%d", &x);
        v.push_back(x); // !
    }
    sort(a, a + 100); // !!
    sort(v.begin(), v.end()); // !!!
}
            

<cstdio>

雖然cin, cout用起來很順手，不過比賽用它遲早會被雷：

速度慢！

#include <cstdio>
using namespace std;
int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d%d", a, b);
}
            

C留下來的函數，所以傳入scanf的變數需要用&（包成指標）。

• %d = int
• %lld OR %I64d (看OS) = long long

<cstdio>

不過如果要輸出浮點數的時候⋯⋯

#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
    double x;
    printf("%.15lf\n", x);
    cout << fixed << setprecision(15) << x << endl;
}
            

<cstdio>

對了，還有字串輸入輸出

字串結尾有一個\0 (ascii 0)

#include <cstdio>
#include <iostream>
using namespace std;
char buf[108]; // 小心\r\n\0
int main() {
    // 機車的事情是這四個東西處理「讀到什麼時候都不一樣
    scanf("%100s", buf); // 讀到空白（包括\n），不讀空白本身
    // buf已經是指標（陣列），所以不用包
    fgets(buf, 100, stdin); // 讀到\n，會讀\n本身，還會放進buf
    cin.get(buf, 100); // 讀到\n，不讀\n本身
    cin.getline(buf, 100); // 讀到\n，會讀\n，但不會寫進buf
}
            

struct

#include <cmath>
struct Point {
    int x;
    int y;
};
Point pts[100];
vector<Point> ptv;
double dist(Point a, Point b) {
    double xd = a.x - b.x;
    double yd = a.y - b.y;
    return std::sqrt(xd * xd + yd * yd);
}
            

為什麼要struct

#include <bits/stdc++.h>
struct Point {
    int x;
    int y;
    // ↓↓↓ 這一行基本上要背起來 ↓↓↓
    bool operator<(const Point & o) const {
        if (x != o.x) return x < o.x;
        return y < o.y;
    }
};
vector<Point> ptv;
int main() {
    // ... 輸入到ptv之類的 ...
    sort(ptv.begin(), ptv.end());
}
            

reference

（中文似乎真的翻做「參考」，不過我覺得「別名」比較貼切）

函數要修改外面傳進來的變數的時候（常常用來回傳多個值）

int egcd(int a, int b, int & ac, int & bc) {
    if (a == 0) { ac = 0; bc = 1; return b; }
    int g = egcd(b % a, a, bc, ac);
    ac -= (b / a) * bc;
    return g;
}
            

<map>

int arr[100], sarr[100];
map<int,int> inv;
int main() {
    for (int i = 0; i < 100; i++) {
        int a;
        cin >> a;
        arr[i] = sarr[i] = a;
    }
    sort(sarr, sarr + 100);
    fori (i, 0, 100) inv[sarr[i]] = i;
    fori (i, 0, 100) {
        cout << arr[i] << " " << inv[arr[i]] << endl;
    }
}
            

<set>

set<int> s;
int main() {
    for (int i = 0; i < 100; i++) {
        int a;
        cin >> a;
        if (s.count(a)) {
            cout << a << endl;
        } else {
            s.insert(a);
        }
    }
}
            

<queue>

（在比賽裡）queue用deque模擬就好了，其實想要的是priority_queue

priority_queue<int,vector<int>,greater<int> > q;
// 傳greater表示希望top要是最小的。
// 邏輯：不傳的結果是less，平常的priority（優先序）要最大的先做。
int main() {
    q.push(1);
    for (int i = 0; i < 10000; i++) {
        int x = q.top();
        q.pop();
        q.push(x * 2);
        if (x % 2 == 0) q.push(x * 3);
    }
    printf("%d\n", q.top());
}
            

STL etc.

• <deque>, <list>
• <queue> → priority_queue
• <set> → multiset
• <map> → multimap
• <utility> → pair

cout.precision(15);
cout << setprecision(15) << fixed;
            

預處理器(preprocessor)

千萬不要在競賽或練習以外的場合寫這種鬼東西

#define fori(i,s,e) for (int i = (s); i < ((int)e); i++)
// ↑↑↑ 其他常見寫法：FOR, REP
#define allof(s) (s).begin(), (s).end()
// ↑↑↑ 其他常見寫法：ALL
#define scan_d(x) scanf("%d",&(x))
#define scan_dd(x,y) scanf("%d%d",&(x),&(y))
vector<int> v;
int main() {
    fori (i, 0, 100) {
        int x; scan_d(x);
        v.push_back(i + x);
    }
    sort(allof(v));
}
            

預處理器(preprocessor)

// #define NDEBUG
// ↑↑↑ 也影響到<cassert>
#ifdef NDEBUG
#define debugf(...) ((void)0)
#else
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#endif
            

位元運算

// 也適用於int，不過純粹拿來做位元運算的數通常用unsigned:
unsigned int a; // 0 ~ 2^32 - 1
unsigned long long b; // 0 ~ 2^64 - 1
cin >> a >> b;
cout << (~a) << endl;
cout << (a & b) << endl;
cout << (a | b) << endl;
cout << (a ^ b) << endl; // 不是冪哦
cout << (a << b) << endl; // 跟cout的意義完全不相干
cout << (a >> b) << endl; // 跟cin的意義完全不相干
            

pointer（指標）

C留下來的。通常可以用reference的時候就盡量用reference（不會莫名奇妙爆掉），不過如果要寫複雜的資料結構(treap!!!)就不可避免

struct Node {
  int key;
  Node * lc;
  Node * rc;
  Node(int k): key(k), lc(NULL), rc(NULL) {}
  Node * find(int k) {
    if (k == key) return this;
    if (k < key) return (lc == NULL) ? NULL : lc->find(k);
    return (rc == NULL) ? NULL : rc->find(k);
  }
};
            

iterators / foreach

vector<int> v;
int main() {
    // ... 輸入到v之類的 ...
    for (vector<int>::iterator it = v.begin();
            it != v.end();
            it++) {
        *it *= 2;
    }
    // 下面要編譯器夠新！
    for (int & x : it) { x *= 2; }
    for (auto & x : it) { x *= 2; }
}
// map<int,char>::iterator it
// pair<int,char> p = *it
            

lambda

要編譯器夠新！

int main() {
    int x, y, z;
    auto rotate = [&](){
        int temp = z;
        y = x;
        z = y;
        x = temp;
    };
    cin >> x >> y >> z;
    cout << x;
    rotate();
    cout << x;
    rotate();
    cout << x;
}
            

其他莫名奇妙的運算

真的很少用了，大概只有時限超緊的位元枚舉

unsigned int a;
cin >> a;
cout << __builtin_clz(a) << endl;
cout << __builtin_ctz(a) << endl;
cout << __builtin_popcount(a) << endl;
// __builtin_popcountl(unsigned long)
// __builtin_popcountll(unsigned long long)
            

最無聊的A + B Problem

讀入兩個整數（絕對值不會「很大」），輸出這兩個數字之和

TIOJ 1002

Zerojudge a002 (+必須處理多筆輸入)

iostream version

#include <iostream>
using namespace std;
int main() {
    int a, b;
    while (cin >> a >> b)
        cout << a + b << "\n";
    }
}
            

cstdio version

#include <cstdio>
using namespace std;
int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        printf("%d\n", a + b);
    }
}
            

排序(Sorting)

基本的逃不掉。

動畫支援～VisualSort

Selection Sort（選擇排序法）

先掃描一次，「選擇」最小的元素移到最左邊

再掃描一次，「選擇」第二小的元素移到左邊

再掃描一次，「選擇」第三小的元素移到左邊

⋯⋯

每次掃描，「選擇」剩下元素最小的移到左邊

（如何選擇最小的元素？）

Selection Sort（選擇排序法）

for (int i = 0; i < length; i++) {
    int minIndex = i;
    for (int j = i + 1; j < length; j++) {
        if (a[j] < a[minIndex]) minIndex = j;
    }
    if (minIndex != i) {
        int tmp = a[i]; a[i] = a[minIndex]; a[minIndex] = t;
        // swap(a[i], a[minIndex]); in <algorithm>
    }
}
            

Insertion Sort（插入排序法）

第一個元素不用排序

第二個元素放到第一個元素前面或後面

第三個元素放到前兩個元素前面或中間或後面

第四個元素放到前三個元素某處

⋯⋯

左邊有一串已排序好，每次把右邊的下一個數字「插入」左邊的正確位置

Merge Sort

Divide & Conquer 分而治之

排序左半，排序右半，合併！

• 合併的時候像Selection Sort每次拿最小的，不過因為兩半已經被排序好，所以至多只需要檢查兩個元素

★ VisualSort的動畫其實不準，正統的Merge sort需要額外記憶體暫存（不然合併的時候會一直動到中間的元素，幾乎跟Insertion Sort一樣差）

排序(Sorting)

排序演算法還有很多。有實際用途的包括：

• quicksort
• heap sort
• counting sort
• radix sort

沒有實際用途的包括：

• bubble sort
• gnome sort
• stooge sort
• bogosort
• ...

排序(Sorting)

不過幾乎所有競賽中都輪不到自己寫～

std::sort(v.begin(), v.end());

另外你也可以自訂排序順序，一種方法是在struct定義operator<，另一種是傳函數給std::sort：

bool cmp(int a, int b) {
    // a要在b前面嗎？
    return a > b;
}
            

std::sort(v.begin(), v.end(), cmp);

練習：ZJ a225, a915

時間複雜度

Time Complexity

程式跑得夠快很重要（不然會TLE！）

不過怎麼知道「多快」呢？

時間複雜度

$ time ./fairphoto
real   0m0.771s
user   0m0.763s
sys    0m0.005s
$ time ./fairphoto
real   0m0.765s
user   0m0.758s
sys    0m0.005s
$ time ./fairphoto
real   0m0.781s
user   0m0.773s
sys    0m0.006s
$ time ./fairphoto
real   0m0.778s
user   0m0.771s
sys    0m0.005s
            

時間複雜度

不能只用跑的⋯⋯

for (int i = 0; i < length; i++) {
    int minIndex = i;
    for (int j = i + 1; j < length; j++) {
        if (a[j] < a[minIndex]) minIndex = j;
    }
    if (minIndex != i) {
        swap(a[i], a[minIndex]);
    }
}
            

那一步會被跑最多次？

時間複雜度

for (int i = 0; i < length; i++) {
    int minIndex = i;
    for (int j = i + 1; j < length; j++) {
        if (a[j] < a[minIndex]) minIndex = j;
    }
    if (minIndex != i) {
        swap(a[i], a[minIndex]);
    }
}
            

檢查j < length會被執行n(n+1)/2次

j++會被執行n(n-1)/2次。

a[j] < a[minIndex]會被執行n(n-1)/2次。(n = length)

minIndex = j;會被執行0次~n(n-1)/2次。

可是還是不能直接算出處理器要幾「步」

100000e54: 44 8b 1d bd 01 00 00  mov    0x1bd(%rip),%r11d
100000e5b: 45 85 db              test   %r11d,%r11d
100000e5e: 7e 5a                 jle    100000eba <__Z7selsortv+0x6a>
100000e60: 41 b8 01 00 00 00     mov    $0x1,%r8d
100000e66: 45 31 d2              xor    %r10d,%r10d
100000e69: 48 8d 15 b0 01 00 00  lea    0x1b0(%rip),%rdx
100000e70: 4d 8d 4a 01           lea    0x1(%r10),%r9
100000e74: 45 39 d9              cmp    %r11d,%r9d
100000e77: 4c 89 c1              mov    %r8,%rcx
100000e7a: 44 89 d7              mov    %r10d,%edi
100000e7d: 7d 3b                 jge    100000eba <__Z7selsortv+0x6a>
            

@_@

怎麼辦？

Big-O Notation

c₁n(n+1)/2 + c₂n(n-1)/2 + c₃n + …

(c₁/2 + c₂/2) × n² + …

O(n²)

f(x) ∈ O(g(x)) ⇔ ∃ M, x₀ s.t. ∀ x > x₀, |f(x)| ≤ M|g(x)|

（更嚴謹的話可以寫Big-Theta Notation: Θ(n²)）

Big-O Notation

通常常數不會太大，演算法要跑完的重點是當n很大的時候造成的時間成長

目標大概是「10⁷件事情」

Big-O Notation

Wikipedia | 維基百科

Big-O Notation例外

Codeforces 207 Div 1 D: Bags and Coins

不用位元運算硬壓到常數÷32就會

• TLE
• TLE
• TLE
• TLE

不過這種題目很少

Merge Sort?

花的時間叫做T(n)

排序左半 → T(n/2)

排序右半 → T(n/2)

合併：O(n)

T(n) = 2T(n/2) + kn

???

Merge Sort?

Merge Sort?

O(n log n)，也是一般*排序最好的速度

嚴謹／一般做法，參見Master Theorem

Exponentiation

其實競賽中幾乎永遠都是Modular exponentiation，因為大數又難寫又把複雜度搞得亂七八糟

「請輸出答案mod 10⁹ + 7」（是質數）

Exponentiation

10^123456789 mod 10⁹ + 7

long long p = 1;
for (int i = 0; i < 123456789; i++) {
    p = (10 * p) % 1000000007;
}
            

Exponentiation

10^123456789 = 10^123456788 × 10 mod 10⁹ + 7

10^123456789 = 10^123456787 × 10 × 10 mod 10⁹ + 7

10^123456789 = 10^123456786 × 10 × 10 × 10 mod 10⁹ + 7

如果是競賽這樣算大概會TLE，不過自己跑應該還是跑得出來

挑戰計算：2¹⁰¹⁶ mod 10¹⁷ + 3

Hint: 10^123456789 = 10^61728394 × 10^61728394 × 10

這樣乘會爆long long的說

對不起我錯了

小心的話，在蠻大的mod下面乘兩個long long還是做得到的啦：

long long mmul(long long a, long long b) {
    long long res = 0;
    while (a) {
        if (a % 2 == 1) res = (res + b) % MOD;
        a /= 2;
        b = (b * 2) % MOD;
    }
    return res;
}

會做了嗎？

Dynamic Programming (DP)

並非單一演算法，而是一套想法，可以發展很多演算法。

Dynamic Programming (DP)

把一個問題切成小塊。

重複子問題overlapping subproblems

最佳子結構optimal substructure

Dynamic Programming (DP)

Fibonacci

int fibo(int ix) {
    // F(0) = 0, F(1) = 1
    if (ix == 0 || ix == 1) return ix;
    return fibo(ix - 1) + fibo(ix - 2);
}
            

跑跑看？

Dynamic Programming (DP)

fibo(10)

fibo(9) + fibo(8)

fibo(8) + fibo(7) + fibo(8)

fibo(8) + fibo(7) + fibo(8)
Overlapping Subproblems!

Dynamic Programming (DP)

Fibonacci: Bottom-Up

int fibo[50];
void init() {
    fibo[0] = 0;
    fibo[1] = 1;
    for (int i = 2; i < 50; i++) fibo[i] = fibo[i-1] + fibo[i-2];
}
            

Dynamic Programming (DP)

Fibonacci: Top-Down (Memoization)

int _fibo[50];
void init() {
    for (int i = 0; i < 50; i++) _fibo[i] = -1;
}
int fibo(int ix) {
    if (_fibo[ix] != -1) return _fibo[ix];
    if (ix == 0 || ix == 1) return _fibo[ix] = ix;
    return _fibo[ix] = fibo(ix - 1) + fibo(ix - 2);
}
            

當然不是永遠那麼容易

問題是「如何決定什麼是子問題？」

要求：

• 「如果我知道子問題的解，就知道原問題的解」
  • 「如果我知道子問題的子問題的解，就知道子問題的解」
• 「子問題不太多」

經驗

Longest Common Subsequence

Intro: Subsequence 子序列

"dynamicprogramming"

"dynamicprogramming" → "program"

"dynamicprogramming" → "ioi"

"dynamicprogramming" → ""

"dynamicprogramming" → "dynamicprogramming"

LCS 最長子序列

"dynamicprogramming" vs "algorithms"

"dynamicprogramming" vs "algorithms" → "agri"

哪裡有子問題？

LCS 最長子序列

"dynamicprogramming" vs "algorithms"

• "dynamicprogrammin" vs "algorithms"
• "dynamicprogramming" vs "algorithm"

有用嗎？為什麼？

如果紅色的字母是同一個呢？

for (int i = 1; i <= an; i++) {
    for (int j = 1; j <= bn; j++) {
        dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        if (a[i-1] == b[j-1])
            dp[i][j] = max(dp[i][j], 1 + dp[i-1][j-1]);
        printf("%d ", dp[i][j]);
    }
    printf("\n");
}
            

LCS 最長子序列

• ZJ c001
• ZJ a252
• HOJ 31
• Codeforces R#264 Div 2 B
• Codeforces R#201 Div 1 B

背包問題

total 100kg → $?

有三種版本：01，無限，Fractional

第三種不需要DP（為什麼？）

背包問題

全部檢查？O(2ⁿ)

其他子問題？

100kg → $? | 86kg → $?

| 72kg → $? | 58kg → $? | 44kg → $? | 30kg → $? | 16kg → $? | 2kg → $?

背包問題

Zerojudge d862 a455 a350

自己試試看

TIOJ 1007, 1014, 1019, 1029

Codeforces R#260 Div1A, RCC 2014 Div2A, R#240 Div1B