题面
给定一个n个正整数的序列{(a_n)}，在这个序列上我们可以执行收缩操作。一次收缩操作可指定一个i，使(a_i)-(a_{i+1})替换(a_i),(a_{i-1})。对于n个整数的序列，我们可以执行n-1个不同的收缩操作，每个收缩操作都会产生一个新的长度为n-1序列。现给定序列{(a_n)}和目标数t，求一个n-1操作序列，使最后得到t。1<=n,(a_i)<=100，1<=t<=1000
链接：http://poj.org/problem?id=1722
思路
设最终答案为ans，ans一定会加上(a_1)减去(a_2)。在一个操作序列进行完操作后，若(a_k)最终为减号时，(a_{k+1})最终为加号时，对k进行操作，把(a_{k+1})先减到(a_k)上 ，因为后面a_k一定会减，所以(a_{k+1})最终就是加号了。对所有这样的一对数先进行操作，最后会只剩下为加号的(a_1)，和一堆最终为减号的(a_k)，这时候我们一直对1进行操作，最后(a_k)就都会是减号。综上只有(a_1),(a_2)的符号是固定的，(a_k)的符号无论加减都至少有一种操作序列满足要求。所以我们不有考虑不好维护的每一次操作的瞬时状态，而是考虑容易维护的最终状态，再结合前面的过程求得答案。具体就是把题目划为两个部分，一部分设(f_i,_j)来表示操作到a_i时，能否使结果为j，转移方程：
(f_i,_j=f_{i-1},_{j+a_i}|f_{i-1},_{j-a_i})
并保存路径即(a_i)前面的加减号。一部分由加减号来构造一个符合要求的操作序列。
代码
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N=110,M=1e4+10;
short path[N][M<<1],a[N],f[N][M<<1],an[N];
void dfs(int i,int j)
{
if(i==2) return;
if(path[i][j]) dfs(i-1,j+a[i]);
else dfs(i-1,j-a[i]);
an[i]=path[i][j];
}
int main()
{
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int n,k,last,cnt=1;
scanf("%d%d",&n,&k);
if(n==1) return 0;
if(n==2)
{
printf("1
");
return 0;
}
for(int i=1;i<=n;i++) cin>>a[i];
f[1][M+a[1]]=f[2][M+a[1]-a[2]]=1;
for(int i=3;i<=n;i++)
{
for(int j=1;j<(M<<1);j++)
{
if(j-a[i]>0&&f[i-1][j-a[i]]) f[i][j]=1,path[i][j]=0;
if(!f[i][j]&&j+a[i]<(M<<1)&&f[i-1][j+a[i]]) f[i][j]=1,path[i][j]=1;
if(!f[i][j]) path[i][j]=-1;
}
}
dfs(n,M+k);
last=2;int in=0;
for(int i=3;i<=n;i++)
{
if(!an[i]) printf("%d
",last),in++;
else last=i-in,cnt++;
}
for(int i=1;i<=cnt;i++) printf("1
");
return 0;
}