题形：DP，背包
题意：有一个数组，里面保存着n个数。con(i) 操作表示 把a[i] 和 a[i+1] 这两项 用 a[i]-a[i+1]这一项取代（所以操作结束后数组长度会减少1）。通过n-1次操作，可以让数组只剩下一个数。给你一个目标数，求n-1次操作，使得经过这些操作之后这个数组能变成这个目标数（题目保证存在解）
思路：
题目拐了个大弯啊~隐藏的真好。需要转换模型。
首先，容易把题意转变成，a[1]-a[2]-a[3]-...-a[n]，这样一个算式，让你加括号，使得结果为目标数
然后想象一下最后的答案。假设我们知道最后的答案，那么把所有括号拆掉，结果的式子一定一这样的：a[1]-a[2]±a[3]±a[4]±...±a[n] = 目标数
再转。把前两个符号确定的移走，就成了±a[3]±a[4]±...±a[n] = 目标数-a[1]+a[2].
左边已经很像背包了，要么正，要么负。如果变成，要么有，要么没有，那就完全是背包了。怎么变呢？
2*a[3] 2*a[4] 2*a[5] ... 2*a[n] = 目标数-a[1]+a[2] + (a[3]+a[4]+a[5]+...+a[n])
这样，对于左边的某个2*a[i],如果取，那么就表示这个数原来的符号是+，如果不取，就是-。
最后是还原回操作。本来以为不可操作，实际挺简单的。
观察：
a-b+c+d-e+f-g
= a-(b-c-d) - (e-f) - g
= a-((b-c)-d) - (e-f) - g
也就是说，从左往右扫过来，如果数a[i]的符号为正，则让它与左边的数合并。最后，所有的数都和1合并。就行了。
这里需要注意，合并以后造成的坐标变化。我的实现是：
re[i] 保存第i个数在最优解中是否被取
stk[i] 保存所有被取的数（从左到右）
则：
for (int i = 0; i < n-2; i++) { if (re[i] == 1) st[top++] = i+2;//+2纯为数出来的。反正是差个系数 } for (int i = 0; i < top; i++) { st[i] -= i; //前面已经合并了i次，所以少了i个 }
代码：
#include <cstdio> #include <cstring> #include <cstdlib> #define V 30000 #define N 200 int c[N]; int dp[V]; int record[N][V]; int re[N]; int st[N]; int main() { int n,t; while (~scanf("%d%d", &n, &t)) { int a, b; if (n == 1) { scanf("%d", &a); continue; } if (n == 2) { scanf("%d%d", &a, &b); printf("%d ", 1); continue; } scanf("%d%d", &a, &b); int sum = 0; for (int i = 0; i < n-2; i++) { scanf("%d", &c[i]); sum += c[i]; c[i] *= 2; } int v = sum-a+b+t; //assert v > 0 for (int i = 0; i <= v; i++) { dp[i] = 0; } for (int i = 0; i < n-2;i++) { for (int j = v; j - c[i] >= 0; j--) { if (dp[j] > dp[j-c[i]]+c[i]) { record[i][j] = 0; } else { dp[j] = dp[j-c[i]]+c[i]; record[i][j] = 1; } } } //printf("dp = %d(v= %d) ", dp[v], v); int nowv = v; for (int i = n-2-1; i >= 0; i--) { if (record[i][nowv] == 1) { re[i] = 1; nowv -= c[i]; } else re[i] = 0; } int top = 0; for (int i = 0; i < n-2; i++) { if (re[i] == 1) st[top++] = i+2; } for (int i = 0; i < top; i++) { st[i] -= i; } for (int i = 0; i < top; i++) { printf("%d ", st[i]); } for (int i = top; i < n-1; i++) { puts("1"); } } return 0; }