?
本文出自 ?? http://blog.csdn.net/shuangde800
?
題目鏈接 ：? 點(diǎn)擊打開鏈接
題目大意
某校有n個(gè)教師和m個(gè)求職者，已知每人的工資和能教的課程集合，要求支付最少的工資使得每門課都至少有兩名教師教學(xué)。在職教師必須招聘。
思路
這題不太好想,搞了很久。。
f[s1][s2]： s1表示課程集合{ s1 }都至少有一個(gè)教師教的情況。
? ? ? ? ? ? ? ?s2表示課程集合{ s2 }都至少有兩個(gè)教師教的情況。
每個(gè)求職者的pi, 對于每個(gè)求職者，要么選，要么不選，就是01背包問題。
對于s1，s2，可以根據(jù)當(dāng)前枚舉到的求職者課程即可，可推出下一個(gè)狀態(tài)：
nextS1 = p[i] | s1,
nextS2 = (p[i] & s1) | s2
f[nextS1][nextS2] = min(f[nextS1][nextS2], f[s1][s2] + p[i])
代碼
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
