USACO/zerosum

分析

DFS

每层只有3个状态，层数最多只有8层，不会超时。（令我非常惊讶的是，没有任何剪枝的DFS最后3-9每个结果都是0.000秒杀。。。表示自己运行时明显有等待时间的。。。难道是USACO电脑太好了？）

枚举时按照' ','+','-'的顺序添加当前空格处的运算符，保证输出的顺序正确。 用sum记录当前加和，用last记录当前的连续数，就是之前添' '连成的数。

' '：sum=sum-last+last*10+s+1(last>0)；sum=sum-last+last*10-s-1(last<0)； 
     last=last*10+s+1(last>0)；last=last*10-s-1(last<0)
'+'：sum=sum+s+1；last=s+1
'-'：sum=sum-s-1；last=-s-1

另一种方法是最后计算是否为0.

注意:PASCAL自带的字符串函数val(s:string;var t:longint)中,s[1]可以为'+'或'-',所以在计算时显得异常简单.（注意'+','-'是首位，表示正负）

通过三进制枚举

实际上，我们也可以用三进制枚举，从3^(n-1)到1，每个数都转化为三进制。2表示' ',1表示'+',0表示'-'。 具体见两个pascal代码。

参考代码

C
C++
Pascal
Java

引用

[1]

[2]