（好了，看了别人写的之后，原来这是可以直接循环实现的，你们可以不用看了...）


注意，我的方法较麻烦，不过我想不出其它方法。

首先，有DP求出前n个数能得到的所有数，记录一下得到这个数字是+还是-的，
+就用0表示，-就用1表示，使用dp[i][j]记录（表示第i与i+1个数之间进行运算后得到值j，因为会出现负数，每一个差都要加上100处理)
dp[i][j]记录这次操作是0还是1；
path[i][j]记录这次操作加上或减去的数k
最后向前迭代即可的得到所有的+-序列

注意第1与第2个数之间的符号一定是-
dp完成后向前迭代把0,1序列存在一个str[]中
str[i]表示i与i+1的操作是0或1

接着分析序列l,..,r(初始时l=1,r=n-1）
定义递归过程process(l,r),与一个全局变量time

每次递归开始时time++（如果l!=r）,用局部变量now记录下当前time值
从后先前扫描，找出第一个i，使i与i+1的操作是-
（如果l!=r，- 操作一定始终存在。）

提取这个减号，str[i+1]到str[l-1]都变号
接着递归处理l，..，i和i+1，..,r
递归过程在l==r时结束，此时返回l
a=process(l,i)
b=process(i+1,r)
（注意process(l,i)与process(i+1,r）的先后顺序)
ans[now]=min(a，b）
递归返回值min(a,b)

这过程有点像建立一颗表达式树

for(i=n-1;i>=1;i--)倒序输出ans[i]

进行表达式树时最后处理的一对先处理肯定不会受影响，并且合并后
这个数的位置就变成了其表达式树中所有叶子中具有最小编号数的编号。

代码

# include <stdio.h>
# include <string.h>

short dp[102][20050];
short path[102][20050];//这里path记录的数是这个数在s中的位置
int s[102],tar;//s是这个数列,tar是目标数

int max(int a,int b)
{
	return a>b?a:b;
}
int min(int a,int b)
{
	return a<b?a:b;
}

int str[102],n,ans[102],time=0;//str是dp完成后得到的+-序列

int process(int l,int r)
{
	if(l==r)	return l;
	int i,j,dd=++time;
	for(i=r-1;i>=l;i--)
	{
		if(str[i]==0)
			break;
	}
	for(j=i+1;j<r;j++)
	{
		str[j]=(!str[j]);
	}
	int a,b;
	b=process(l,i);
	a=process(i+1,r);
	ans[dd]=min(a,b);
	return min(a,b);
}

int main()
{
	int i,j,a;
	scanf("%d %d",&n,&tar);
	for(i=1;i<=n;i++)
		scanf("%d",s+i);
	
	memset(path,0,sizeof(path));
	memset(dp,0x7F,sizeof(dp));
	
	if(n==1||n==2)
	{
		printf("1\n");
		return 0;
	}
	
	int maxv;//目前得到最大的数，只是稍微优化一下用
	dp[1][s[1]-s[2]+100]=0;
	path[1][s[1]-s[2]+100]=2;
	
	maxv=s[1]-s[2]+100;
	
	for(i=2;i<=n-1;i++)
	{
		for(j=1;j<=maxv;j++)//主要j是上一次操作所得到值
		{
			if(dp[i-1][j]>2)	continue;

			dp[i][j+s[i+1]+100]=1;
			path[i][j+s[i+1]+100]=i+1;
			
			dp[i][j-s[i+1]+100]=0;
			path[i][j-s[i+1]+100]=i+1;
			
			maxv=max(maxv,j+s[i+1]+100);
		}
	}
	
	i=n-1;j=tar+100*(n-1);//每次计算差时都+了100,目标数也要加n-1个100
	
	while(i!=0)
	{
		str[i]=dp[i][j];
		if(dp[i][j])
		{
			j-=(s[path[i][j]]+100);
		}else
		{
			j=j-100+s[path[i][j]];
		}
		i--;
	}

	process(1,n);
	for(i=n-1;i>=1;i--)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}