CERC2012 A - kingdoms 状态压缩dp

CERC2012 A - kingdoms 状态压缩dp

题目:

​​Click here​​

题意:

有N个公司..每个公司对每个公司有欠款(负数)或者借款(正数)...一个公司如果借款大于欠款就可能倒闭..一个公司倒闭后其对于得债务关系就都没了..问若最后只存在一个公司,可能是哪些...

题解:

公司倒闭是相继倒闭的..又公司数量不超过20...容易想到状态压缩dp...dp[x]代表在x代表的二进制状态下1代表未倒闭..0代表倒闭了..这种状态是否可以存在..

初始是dp[(1<

找答案..就是看dp[2^0]~dp[2^(n-1)]哪些是true..就是答案....

Program:

#include#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。