一道很奇妙的线性DP,可以证明一个数至多进行两次操作(因为符号只能是‘+’,‘-’)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define gc getchar()
using namespace std;
const int N=105,M=1e4+10;
const int G=10000;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
} 
int f[N][M<<1],a[N],ans[N];
/*
题意就是几个数加或减合在一起 
如果一个数的符号为正,那么它一定是被减掉后消掉的,
因此就输出它前面的符号为‘-’的个数.
而对于剩下的数,符号为‘-’,很明显,我们对1一直操作就行了,
*/
int main()
{
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(a[i]);
    f[1][a[1]+G]=1;//a[1]一定是+ 
    f[2][a[1]-a[2]+G]=-1;//a[2]一定是- 
    for(int i=3;i<=n;i++)
        for(int j=0;j<=(G<<1);j++)/*f[i][j]表示前i个数能否表出j,且第i个是+还是-*/
            if(f[i-1][j])
            {
                f[i][j+a[i]]=1;
                f[i][j-a[i]]=-1;
            }
    int p=m+G;
    for(int i=n;i>=2;i--)
    {
        ans[i]=f[i][p];
        if(ans[i]==1)p-=a[i];
        else p+=a[i];
    }
    int cnt=0;
    for(int i=2;i<=n;i++)
        if(ans[i]==1)
        {
            qw(i-cnt-1);puts("");//前面还剩下多少次操作使i到1,原本为i-1,经历一次合并之后,就变成i-2,这些数减2次(还有一次为与a[1]减)(符号从负变为正。) 
            ++cnt;
        }
    for(int i=2;i<=n;i++)
        if(ans[i]==-1)puts("1");//操作次数为一次,即符号为'-'的 ,仅需与a[1]进行一次减操作就好了。 
    return 0;
}