算法分析

　　我们首先来分析一下题目所给出的开锁规则。注意分析后可以发现，如果把所有的灵异值从左到右依次排列，在每个数之前都填上减号（第一个数除外），那么，每一种操作方案就与一种添括号的方案一一对应。于是，原问题就转化成了求对于一个全部由正整数和减号组成的表达式，是否存在一种添括号的方案，使得表达式的值为一个指定的数。

　　为了简化问题，我们先不考虑应该怎么添括号，而仅仅考虑是否存在一种可行的方案。假设存在一种可行的方案，那么我们对这个添过括号的表达式进行脱括号的化简后，就得到了一个只包含加减运算的表达式。反之，如果一个表达式只由加减号组成，那么一定存在添括号的方案，把加号全部变成减号（这样的方案可能是不唯一的）。因此，问题又转化为对于给出的一列数，在其中添上加减号，问是否能得到一个指定的数。

　　更进一步的，由于我们暂时不考虑具体的添括号方法，次序就显得无关紧要了。因此，我们可以把式子改写成如下形式：
　　
　　　　（其中）
也就是
　　
　　　　（其中）
　　设 ，指定的目标数为obj，
　　，若我们能找到一个t，使得，则所求的方案就是存在的。问题最后转化为求所有可能的t值，也就是从到中取任意个数所能得到的所有和。

　　这样的模型我们已经很熟悉的了，这个问题可以用动态规划的方法来解决。设当前所能得到的所有和构成了集合S，加入一个新的数后，所能得到的和的集合为。集合的操作可以通过boolean型数组完成。具体的实现如下：
　　for i:=1 to n do
　　　for j:=max downto min do
　　　　{max 和 min 分别表示当前得到的和的最大值及最小值}
　　　　　if can[j] then {can[i]的值代表能否取到和 i}
　　　　　　can[j+]:=true;

　　请大家注意，这个循环必须从大到小，否则是错误的。
　　我们来分析一下这个算法的时间复杂度。根据题意，的值在[1,100]之间，最多有5000个数，因此max至多为5000100，算法的时间复杂度为。由于N最大可达到5000，因此这个计算量还是相当大的，很难在题目规定的时限内出现。

　　值得注意的是，的值被限定在了[1,100]内，据此，我们提出一种改进的实现方法，一批一批的处理（即同时处理值相同的所有数）。具体的实现是
　　for i:=1 to 100 do
　　　for j:=max downto min do
　　　　if can[j] then
　　　　　{ now:=j;
　　　　　　for k:=1 to tot[i] do //tot[i]代表值为i的数的个数//
　　　　　　　{ now:=now+i;
　　　　　　　　if not can[now] then can[now]:=true
　　　　　　　　else break;
　　　　　　　}

　　　　}
　　这样虽然不能降低时间复杂度，但却大大减小了实际计算量（最坏情况下的计算量也只有2000000左右）。程序的运行效率有了很大的提高，可以在规定时间内出解。

　　解决了是否有解的问题后，我们来考虑一下有解时应该如何得到操作方案。我们可以在判断过程中加一个数组来记录某个t值是如何得到的，并以此还原表达式。当我们得到所有前的符号（+或-）后，可以按照下面的规则得到操作序列：
　　i:=n
　　repeat
　　　j:=i;
　　　while 的符号与的符号相同 do dec(j)；
　　　输出i-j 个j；
　　　i:=j;
　　until i=1;
　　举个例子，若得到的表达式为
　　　　
　　则3 3 1 1就是一组符合题意的操作方案。

小结

　　通过这道题，我们可以看到，转化问题的模型，使其简单而易于实现，对解题有着重要的帮助。同时，对于同样的算法，不同的实现方法可能带来程序效率的巨大差异，这也是我们在解题过程中应当注意的。