UVA 11691 - Allergy Test(狀壓dp+貪心)

題意：這題題意看了老半天都沒弄懂，好在後面找到個ppt，上面有中文題意- -，不過上面的做法是純貪心，挺巧妙的但是感覺有點不靠譜，

下載下傳位址：

給n種過敏原的存活期，每天可把一種過敏原注入人體內。若有兩個以上過敏原存活於人體中，則無法進行實驗(也就是每種過敏原都必須有一天是單獨存活於人體中)。實驗結束於最後的過敏原死亡的那天，求最短實驗天數。

思路：我的思路是狀态壓縮dp+貪心，20個過敏原做狀态壓縮，然後每次加過敏原的時候，盡量往裡面覆寫，dp[s][k]，s表示過敏原使用狀态，k表示後面通出來單獨存在過敏原的天數，然後選一個新的過敏原去盡量覆寫他，這樣k的一維隻要開到7就夠了，因為每段長度最多就是7。狀态轉移方程為：

dp[k][s] = min{dfs(s^(1<<i), max(0, num[i] - k - 1)) + max(1, num[i] - k)}

代碼：