SUBTRACT

给出一个长度为n序列\(\{a_i\}\)，定义一个操作，记做\(con(a,i)\)，意思是用\(a_i-a_{i+1}\)替代\(a_i,a_{i+1}\)，显然最后一个数字不能进行这样的操作，序列也最多只能进行n-1次操作，而且最后序列会剩下一个数字，求它刚好为t的操作方案，\(1 <= N <= 100,1 <= ai <= 100\)。

解

显然，当前的模型是不能进行递推的，因为序列长度在改变，于是有以下性质

性质1

假设序列为\(\{a,b,c\}\)，进行操作大概如此

a b c

a-b c

a-b-c

a b c

a b-c

a-b+c

于是我们发现所谓的操作，也就是给序列的各个数字前添上+，-号，不难发现第一个数字前必然是+，第2个数字必然是-，问题是不知道后面的+，-序列是否合法，不妨猜测它是合法的，但是暂时没办法证明。

性质2

如果把替代后的数用括号看成一个整体

a b c

a (b-c)

(a-(b-c))

于是发现问题转化为刚开始序列只有第一个数字前面为+，后面的全为-，要添上括号，并保证每一个数都被扩到（也就是碰到括号边界），而我们的加减序列，只是被去掉了括号，这条性质是便于理解。

性质3

性质1留下一个疑问，就是怎样的+，-序列才是合法的，既然不知道，猜测无论如何都是合法的，首先能够发现的是一个加减序列为\(a-b-c-d\)，即第一个+，后面全是-，我们一定能够不停地对第一个数进行操作使之合法，对于只有两个数一定第二个数符号为-才是让这两个数被加上括号，因此关键在+

于是对于一个+，-序列而言，遇到+，我们肯定要想办法变为-，而要使之为-，必然前面要有-，让之变为-，于是对于一段连续的+，我们都可以进行这样的操作，而注意到第二个数一定有一个-，因此无论如何后面有+的数总会有-，因此后面无论+-情况如何，总能成为一个合法的操作序列。

而且也告诉我们，成为操作序列的办法是，遇加变减即可。

有了这三条性质，我们注意到数字很小，现在问题是该数字是选+还是-，让之最后结果正好为t，于是可以暴力压维保存t，因为并没有求最优性问题，递推数组可以顺便保存方案，1表示这里选+，-1表示这里选-，因此设\(f[i][j]\)表示前i个数权值正好为j的i的符号（0表示这是非法状态），用顺转移有

\(if(f[i][j])\)

\[f[i+1][j+a_i]=1,f[i+1][f-a_i]=-1
\]

边界：\(f[1][a_1]=1,f[2][a_2]=-1\)

答案：\(f[n][t]\)

参考代码：

#include <iostream>

#include <cstdio>

#define il inline

#define ri register

#define zero 10000

using namespace std;

int a[101],dp[101][20010],

    ans[101];

void getans(int,int);

int main(){

    int n,t;scanf("%d%d",&n,&t);

    for(int i(1);i<=n;++i)scanf("%d",&a[i]);

    dp[1][zero+a[1]]=1,dp[2][zero+a[1]-a[2]]=-1;

    for(int i(2),j;i<n;++i)

        for(j=0;j<=20000;++j)

            if(dp[i][j])

                dp[i+1][j+a[i+1]]=1,

                    dp[i+1][j-a[i+1]]=-1;

    getans(n,t+zero);int tot(2);

    for(int i(2);i<=n;++i){

        while(ans[i+1]==1&&i<=n)++i,printf("%d\n",tot);++tot;

    }--tot;while(--tot)puts("1");

    return 0;

}

void getans(int a,int b){

    if(!a)return;ans[a]=dp[a][b];

    getans(a-1,b-dp[a][b]*::a[a]);

}

巴特西

SUBTRACT

解

最新文章

热门文章