SRM568 1000pt

很变态的一个idea……
虽然看着题解(内含题目)写的但是还是很有收获
这个思路很好地诠释了brute-force的真正含义
一个50的vector传进来
先是用$$O(\frac{(2*x)!}{2^x})$$的搜索算法解决$$x \le 12$$的情况(x是vector里为-1的元素的数目)
然后对于$$x > 12$$的情况,由于-1是成对出现的,所以$$x \geq 14$$,然后$$2^{\frac{50 – 14}{2}} * 50^2$$搞定剩下的部分。
具体解法涉及到判定二分图的那种01染色,要把模型转化过去并且想到正解真是太不容易,难怪现场没有人搞出来。
更惨的是按照正解写要是太暴力,还是会TLE的。
mark一下。
[code]

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注