n个人围成一个圈，每个人可以看到他自己和下一个人面前的物品，共有n件物品要放置。每件物品每个人要么喜欢要么讨厌，要求出一个物品放置方案，使得满足每个人看到的不都是他讨厌的情况下所有人喜欢的个数和最大。
求出一个可行解的话可以构造一个2-sat。但是那样复杂度已经很高了>___<

诶呀完全不会..

2-sat复杂度不高吧...
还有什么方法?网络流可捉么

网络流不会。。
2-sat有n^2个变量。。。

但是2-sat是O(边数)的吧...输入不就是O(N^2)的么...

边数>>N^2

哦...边数是O(N^3)的>_____________<
那就不会捉了,网络流似乎不好构图

不对。。
这题2-sat不可做。。。
是NPC的。
假定我们加强哈密顿路问题，对于边i->j当且仅当di(i是哈密顿路中的di个)为某些值的时候能走，而哈密顿路问题是这个问题的特殊化，显然解决了这个问题就能解决哈密顿路问题。
那么我们枚举第一个面前放什么，那么下面可以构造出上面的那样一个加强哈密顿路问题，而且这种构造可以存在一个逆对应。
因此这个问题能从哈密顿路归约过来，所以是NPC

哦...傻了,构图不是2-sat的,是多sat的...
最近不搞OI,算法能力为0啊..........