?
本文出自 ?? 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)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
