uv-1084,uva11059

　　标题链接：

　　http://uva.onlinejudge.org/index.php?option=com _ online judge Itemid=8 category=457 page=show _ problem problem=1258

　　1.先把方程的项移动一下，假设原来的项是1 ^ 2=4-5 ^ 6，那么移动后就变成了1 ^ 2-4 ^ 5 ^ 6=0。并计算所有数字的和，sum，以及等式左边的正数plusNum。

　　2.然后演变成“从N个数中选出sum/2之和的plusNum个数组成一个正部”，因为如果等式成立，那么所有正数之和的绝对值和所有负数之和的绝对值一定相等。如果为真，对于每一个数，要么取，要么不取，复杂度就变成了2 ^ 16。

　　3.分支剪枝：1)如果每次递归中当前值加上要选择的数之和大于sum/2，则不选择。

　　2)如果所有数的和都是奇数，那么直接无解。这个优化挺大的，直接从1.9s降到了0.08s然而我真的不知道Orz是怎么从rank No.1神牛的0.02s中走出来的。

　　#包括cstdio

　　#包括cstring

　　const int maxn=1000

　　char str[10000]；

　　char sigma[maxn]；

　　bool vis[maxn]；

　　int num[maxn]，ans[maxn]，n，idx

　　int加[maxn]，leftNum，plusNum，sum

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。