TOJ 126. Irritation
===
###### tags: `Ans`

#### 先備知識
* 二分搜 [by sa072686](https://hackmd.io/@sa072686/APCS_HARD/https%3A%2F%2Fhackmd.io%2Fs%2Frk_5Ee0K7)
* DFS [by sa072686](https://hackmd.io/@sa072686/APCS_HARD/https%3A%2F%2Fhackmd.io%2Fs%2Fr18hJX1TX)

## 想法
題目要求: **所有可能分數中的, 第一個大於等於詢問的分數**
例如:
可能有: `10, 20, 38, 56, 76`
詢問 20, 輸出 20
詢問 35, 輸出 38
詢問 50, 輪出 56

我們把所有可能性算出來, 再利用 `lower_bound` 搜出答案

## 暴力
打算生成所有解的話, 可能打算這樣做

int sco[maxN]; // 所有配分
int pos[maxS], r=0;

void gen (int m, int s) //m:= 現在己經選了 m 題; s:= 現在的累積分數
{
	if (m==0)
	{
		pos[r++] = s;
        return;
	}
	gen(m-1,s+sco[m-1]);
	gen(m-1,s-sco[m-1]);
}

## 建表
上面做能拿到前二筆子仼務, 我們可以估一下複雜度
每個 n 都有兩種可能性可以展開, 因此看似有 $2^n$ 種分數, 而 $n \geq 100$, 則有最多 $2^{100}$ 種可能要計算

仔細看題目保證 `| 分數 | ≤ 滿分 ≤ 10000`
可知在計算過程中, 有很多重複的分數出現

又如果 DFS 時 m 相等且 s 相等, 則以人後所有可能出現的分數一樣
我們用一個 vis 表, 記碌每組 m,s 是否已經有人算過了
如果算過了就可以跳過

:::danger
注意分數有負的, 下面的程式碼沒有解決這個問題, 可以自己想想
:::

bool vis[maxN][maxS<<2];
int pos[maxS], r=0;

void gen (int m, int s)
{
    if (vis[m][s]) return; // wrong
    vis[m][(s)] = 1; // wrong
    
    if (m==0)
    {
        pos[r++] = s;
        return;
    }
    gen(m-1,s+sco[m-1]);
    gen(m-1,s-sco[m-1]);
}

## 歐亞文明的發展與交會
其實可以快
樂建答案
表的啦
好方
便