題目連結：
題目大意：
給定兩正整數 ｎ 、 Ｔ （１ ≦ ｎ ≦ １０, ０００，１ ≦ Ｔ ≦ １, ０００），代表接下來有ｎ列輸入。每列輸入給定三正整數 ｓ 、 ｖ 、 ｐ （１ ≦ ｓ ≦ １, ０００ ，１ ≦ ｖ ≦ １０ ^ ９ ， ｐ ＝ １ 或 ２），代表一位女生所需最多的陪伴時間、可以得到的好感度、以及類型。
ｐ ＝ １ ，代表第一類女生，每陪伴他們一單位的時間可以得到其 ｖ ÷ ｓ 的好感度； ｐ ＝ ２ ，代表第二類女生，要完整地陪伴他們 ｓ 單位時間，才能得到 ｖ 的好感度。
現在有 Ｔ 單位的時間可供使用，求最大可獲得的好感度為何？
範例輸入：
//sample input 1
4 10
5 15 2
5 14 2
4 13 2
8 17 2
//sample input 2
4 10
5 15 2
5 14 2
4 13 2
8 17 1
範例輸出：
//sample output 1
29
//sample output 2
30
解題思維：
可以看到這其實就是背包問題（Knapsack）的變形，即時間 → 重量、好感度 → 價值。
如果單純地只有第二類女生，我們可以看到其問題的解法就是直接套上 01 背包的解法。如這題。
而比較麻煩的是第一類女生。但是可以把他們看作 ｓ 個第二類女生，且每個女生之 ｓ ＝ １ 、 ｖ ＝ 原本的 ｖ ÷ 原本的 ｓ 。但是直接套用原本的解法的話，女生的「數量」會太多。
因此，我們需要將第一類女生的陪伴時間 ｓ 分作 １ 、 ２ 、 ４ 、 ８ 、 …… 、 ２ ^ ｋ 以及最後剩下的 ｓ － ２ ^ （ｋ ＋ １） ＋ １ 這 ｋ ＋ １ 個部分。也就是把這個女生的 ｓ 分成大約 log ｓ 的部分。
然後將這些部分視作新的第二類女生（ｓ ＝ ２ ^ ｉ ， ｖ ＝ 原本的 ｖ ÷ ｓ × ２ ^ ｉ），然後套用原本的 01 背包解法即可。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
