acw316.减操作

题意：

• 给定一个数组$a_1,a_2,…,a_n$。
• 定义数组第$i$位上的减操作：把$a_i$和$a_{i+1}$换成$a_i-a_{i+1}$。
• 用$con(a,i)$表示减操作，可以表示为：
• $con(a,i)=[a_1,a_2,…,a_{i-1},a_i-a_{i+1},a_{i+2},…,a_n]$.
• 长度为$n$的数组，经过$n-1$次操作后，就可以得到一个整数$t$。
• 给定数组以及目标整数，求完整操作过程。

思路：

• 假设说有个序列有三个数字$a_1\ a_2\ a_3$。
• 之后进行一次减操作：$a_1，a_2-a_3$。
• 再做一次减操作：$a_1-a_2+a_3$。
• 最后得到的就是一个数字，可以发现，$a_3$虽然在一开始被减去了，但是最后变成+了。
• 所以其实我们关心的是前面每个数字的正负号。
• 而且可以发现$a_1$一定是正号，$a_2$一定是负号，其他的不一定。
• 设$f(i,j)$表示计算到第$i$个数时，结果为$j$时，$a_i$的符号。
• $f(i,j)=1$表示正号，为$-1$表示负号，为$0$表示当前结果无法取到$j$。
• 假如$f(i-1,j)\neq 0$，那么有$f(i,j+a(i))=1,f(i,j-a(i))=-1$。
• 最后通过$f(n,t)$倒推方案。
• 取正好的元素可以看成进行了两次减操作，因此可以先对取正号的元素进行一次减操作，之后再对每个元素进行一次减操作即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 10;
const int d = 10000+1;
int n, t, a[maxn], f[maxn][d*3];
int ans[maxn];

void dp()
{
    f[1][a[1]+d] = 1;
    f[2][a[1]-a[2]+d] = -1;
    for(int i = 3; i <= n; i++)
        for(int j = -10000+d; j <= 10000+d; j++)
        {
            if(f[i-1][j] != 0)
            {
                f[i][j+a[i]] = 1;
                f[i][j-a[i]] = -1;
            }
        }
}

void print()
{
    int s = t + d;
    for(int i = n; i >= 1; i--)
    {
        ans[i] = f[i][s];
        s -= ans[i]*a[i];
    }
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(ans[i] == 1)
        {
            printf("%d\n", i - cnt - 1);
            cnt++;
        }
    }
    for(; cnt < n-1; cnt++) puts("1");
}

int main()
{
    cin >> n >> t;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    dp(); print();
    return 0;
}