题解：P10960 SUBSTRACT

· · 题解

本题其实很简单，不过转化的那一步对于不熟悉的同学来讲有点困难。

首先，因为我们要做很多次减法，我们很容易想到可以把括号拆开，变成加法和减法混合。不过要注意：a_1 永远是做加法，a_2 永远做减法。具体原因也很好想，这里不做解释。

于是这个题就变成了：除 a_1,a_2 以外的其他数可以做加法或减法，问最终如何凑出给定的数 T。

这就是一个很板的 DP 题了，因为最后要输出方案，所以我们需要多记录一下转移到当前状态的上一个状态是什么：

f[1][a[1]+B]=1;
f[2][a[1]-a[2]+B]=1;
la[2][a[1]-a[2]+B]=a[1]+B;
for(int i=3;i<=n;i++)
{
  for(int j=a[i];j<=2*B;j++)
  {
    if(f[i-1][j])
    {
      la[i][j-a[i]]=j;
      f[i][j-a[i]]=1;
    }
  }
  for(int j=0;j+a[i]<=2*B;j++)
  {
    if(f[i-1][j])
    {
      la[i][j+a[i]]=j;
      f[i][j+a[i]]=1;
    }
  }
}

现在就是要考虑如何构造方案了。

我们首先逆向枚举得出每一个数是做的加法还是减法：

void print(int x,int y)
{
    if(x==1)
    {
        return;
    }
    if(la[x][y]+a[x]==y)
    {
        b[x]=1;//做加法
        print(x-1,la[x][y]);
    }
    else
    {
        b[x]=-1;//做减法
        print(x-1,la[x][y]);
    }
}

然后我们思考如何去构造。

因为我们知道这样一个等式：

-(a_i-a_{i+1}-a_{i+2}-\dots)=-a_i+a_{i+1}+a_{i+2}+\dots

所以我们可以把所有做加法的数全部归到前一个做减法的数上。也就是说：如果当前这个数做的是减法，那么我们就先用这个数减去后面连续的做加法的数：

for(int i=n;i>=2;i--)
{
  if(b[i]==1)
  {
    len++;
  }
  else
  {
    while(len--)
    {
      write(i);
      putchar('\n');
    }
    len=0;
    cnt++;
  }
}

最后我们会得到这样一个数列：

a_1-b_2-b_3-\dots

这时我们再用第一个数一直减后面的数就行了：

while(cnt--)
{
  write(1);
  putchar('\n');
}

连起来就是完整代码：

#include<bits/stdc++.h>
#define int long long
#define code using
#define by namespace
#define plh std
code by plh;
namespace fastio
{
    inline int read()
    {
        int z=0,f=1;
        char c=getchar();
        if(c==EOF)
        {
            exit(0);
        }
        while(c<'0'||c>'9')
        {
            if(c==EOF)
            {
                exit(0);
            }
            if(c=='-')
            {
                f=-1;
            }
            c=getchar();
        }
        while(c>='0'&&c<='9')
        {
            z=z*10+c-'0';
            c=getchar();
        }
        return z*f;
    }
    inline void write(int x)
    {
        if(x<0)
        {
            putchar('-');
            x=-x;
        }
        static int top=0,stk[106];
        while(x)
        {
            stk[++top]=x%10;
            x/=10;
        }
        if(!top)
        {
            stk[++top]=0;
        }
        while(top)
        {
            putchar(char(stk[top--]+'0'));
        }
    }
    inline void write(string s)
    {
        for(auto i:s)
        {
            putchar(i);
        }
    }
}
using namespace fastio;
int n,k,a[106],la[106][20006],b[20006];
bool f[106][20006];
const int B=10000;
void print(int x,int y)
{
    if(x==1)
    {
        return;
    }
    if(la[x][y]+a[x]==y)
    {
        b[x]=1;
        print(x-1,la[x][y]);
    }
    else
    {
        b[x]=-1;
        print(x-1,la[x][y]);
    }
}
signed main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    f[1][a[1]+B]=1;
    f[2][a[1]-a[2]+B]=1;
    la[2][a[1]-a[2]+B]=a[1]+B;
    for(int i=3;i<=n;i++)
    {
        for(int j=a[i];j<=2*B;j++)
        {
            if(f[i-1][j])
            {
                la[i][j-a[i]]=j;
                f[i][j-a[i]]=1;
            }
        }
        for(int j=0;j+a[i]<=2*B;j++)
        {
            if(f[i-1][j])
            {
                la[i][j+a[i]]=j;
                f[i][j+a[i]]=1;
            }
        }
    }
    print(n,k+B);
    int len=0,cnt=0;
    for(int i=n;i>=2;i--)
    {
        if(b[i]==1)
        {
            len++;
        }
        else
        {
            while(len--)
            {
                write(i);
                putchar('\n');
            }
            len=0;
            cnt++;
        }
    }
    while(cnt--)
    {
        write(1);
        putchar('\n');
    }
    return 0;
}