题解 【POJ1722】 SUBTRACT

先讲下题目意思

给定一个长度为(n)的序列((1 leq n leq 100)),

每次合并两个元素(i,i+1),即将(i,i+1)变为一个新的元素,权值为(a[i]-a[i+1])((a)为权值),

求在(n-1)次合并后剩下的元素的权值为(t)((-10000 leq t leq 10000))的步骤(保证有解,spj)

解析

这题的减法有点不好弄啊...

但是,仔细想想,

如果我们将(j)和(k)合并成((j-k)),

再将(i)和((j-k))合并,

就变成了(i-j+k),

所以,有些减法在运算时就已经消掉了!!

因此,我们只需要在每个数字前面填上加号或减号,使结果等于(t)就行了.

并且,注意到,第二个元素前只能是减号,因为前面已经不能消掉它的减号了.

然后,用DP递推地求符号就行了.

那么,怎么求呢?

我们可以设(f[i][j])表示加到第(i)个数总和为(j)时第第(i)个数的符号,(1)为加,(-1)为减,

那么,在转移时,若(f[i-1][j])不为零,即前面能够加到(j),

那么,(f[i][j+a[i]])的符号就为正,(f[i][j-a[i]])的符号就为负,

于是,最后从(t)倒推就行了,

不过注意,由于(t)可能为负,所以在求之前可以先加上一个值再算.

最后,注意输出方案,

首先我们可以记录下操作了几步,

由于我们是从前往后扫,所以每次用编号减掉操作次数就行了.

如果一个数的符号为正,那么它一定是被减掉后消掉的,

因此就输出它前面的标号减操作次数.

而对于剩下的数,很明显,我们对(1)一直操作就行了,

因此,若符号为负,输出(1)即可.

(讲的不清楚的地方自己算一下吧.)

上代码吧:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

inline int read(){
	int sum=0,f=1;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return f*sum;
}

const int ret=10000;//加上一个数把t变成非负的
int n,m,sum;
int a[100001];
int f[101][20005];
int op[100001];

int main(){
	n=read();m=read();//m就是t,习惯而已qwq
	for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i];
	sum=ret<<1;
	f[2][a[1]+ret-a[2]]=-1;f[1][a[1]+ret]=1;
	for(int i=3;i<=n;i++){		
		for(int j=0;j<=sum;j++){
			if(!f[i-1][j]) continue;
			if(j+a[i]<=sum) f[i][j+a[i]]=1;
			if(j-a[i]>=0) f[i][j-a[i]]=-1;
		}
	}//DP
	sum=m+ret;
	for(int i=n;i>=2;i--){		
		op[i]=f[i][sum];
		sum-=a[i]*op[i];
	}//求最后的符号
	int tot=0;
	for(int i=2;i<=n;i++) if(op[i]==1) printf("%d
",i-1-tot),tot++;
	for(int i=2;i<=n;i++) if(op[i]==-1) puts("1");
	return 0;
}