题意

给定一个整数数组$a_1, a_2, \cdots, a_n$。 定义数组第i位上的减操作：把$a_i$和$a_{i + 1}$换成$a_i - a_{i + 1}$。 用$con(a, i)$表示减操作，可以表示为： $con(a, i) = [a_1, a_2, \cdots, a_{i - 1}, a_i - a_{i + 1}, a_{i + 2}, \cdots, a_n]$ 长度为$n$的数组，经过$n - 1$次减操作后，就可以得到一个整数t。 例如数组$[12, 10, 4, 3, 5]$经过如下操作可得到整数4： $con([12, 10, 4, 3, 5], 2) = [12, 6, 3, 5]$ $con([12, 6, 3, 5], 3) = [12, 6, -2]$ $con([12, 6, -2], 2) = [12, 8]$ $con([12, 8], 1) = [4]$ 现在给定数组以及目标整数，求完整操作过程。

解题思路

首先分析子问题划分，发现$a_1$对答案贡献必为正，尝试将子问题划分为$a_2, a_3, \cdots, a_n$组成$t - a_1$，但此思路因后续元素符号不确定而受阻。得到关键信息：$a_1$贡献为正，$a_2$贡献为负，其余元素符号不确定。$a_n$贡献符号取决于合并次数，奇数次为负。题目等价于$a_1 \sim a_n$通过加减组合得$t$。提出猜想：当$n \geq 3$时，$a_3 \cdots a_n$正负可任意组合。以三个元素$a_{i-1}, a_i, a_{i+1}$（$i > 3$）为例：需$a_{i+1}$与$a_i$同号，先合并$a_{i-1}, a_i$，再合并$a_{i+1}$；需$a_{i+1}$与$a_i$异号，先合并$a_i, a_{i+1}$，再合并$a_{i-1}$。控制$a_{i+1}$合并次数奇偶，可确定其贡献符号。最终问题转化为：$a_1$为正，$a_2$为负，$a_3 \sim a_n$正负任意组合得$k$。由于$n = 100$，暴力不可行，利用数值范围，定义$dp[i][j]$：前$i$个元素组合结果为$j$，第$i$个元素贡献符号（正为$1$，负为$-1$）。

标程

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ll long long 
#define ull unsigned long long
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 20007;
int dp[107][maxn], num[107], flag[maxn];

int main() {
    int n, t;
    cin >> n >> t;
    t += 10000;
    for (int i = 1; i <= n; i++) {
        scanf("%d", num + i);
    }
    dp[2][10000 + num[1] - num[2]] = -1;
    for (int i = 3; i <= n; i++) {
        for (int j = 20000 ; j > 0; j--) {
            if (j - num[i] >= 0 && dp[i - 1][j - num[i]] != 0) {
                dp[i][j] = 1;
            }
            if (j + num[i] <= 20000 && dp[i - 1][j + num[i]] != 0) {
                dp[i][j] = -1;
            }
        }
    }

    int now_i = n, now_num = t;
    while (now_i > 1) {
        flag[now_i] = dp[now_i][now_num];
        now_num += -flag[now_i] * num[now_i];
        now_i--;
    }

    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (flag[i] > 0) {
            cout << i - cnt - 1 << endl;
            cnt++;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (flag[i] < 0) {
            cout << 1 << endl;
        }
    }
    return 0;
}