给定一个整数数组a1,a2,…,an。
定义数组第 i 位上的减操作:把ai和ai+1换成ai−ai+1。
用con(a,i)表示减操作,可以表示为:
con(a,i)=[a1,a2,…,ai−1,ai−ai+1,ai+2,…,an]
长度为 n 的数组,经过 n-1 次减操作后,就可以得到一个整数t。
例如数组[12,10,4,3,5]经过如下操作可得到整数4:
con([12,10,4,3,5],2) = [12,6,3,5]
con([12,6,3,5] ,3) = [12,6,-2]
con([12,6,-2] ,2) = [12,8]
con([12,8] ,1) = [4]
现在给定数组以及目标整数,求完整操作过程。
输入格式
第1行包含两个整数n和t。
第2..n+1行:第i行包含数组中的第 i 个整数ai。
输出格式
输出共n-1行,每行包含一个整数,第 i 行的整数表示第 i 次减操作的操作位置。
数据范围
1≤n≤100,
−10000≤t≤10000,
1≤ai≤100
输入样例:
5 4
12
10
4
3
5
输出样例:
2
3
2
1
算法1 背包
设
sum=a[1]+a[2]+...+a[n]
`t=a[1]-a[2]±a[3]±..±a[n]`
想要求出t,必定要确定每个数前的符号。
通过这两个式子我们可以求出前面符号为负号的数的和。
设前面的符号为负号的数的和为s;
s=(sum-t)/2; (两式相减正项抵消,负项增加一倍)
但是a[1]前面必定是‘+’,a[2]前面必定是‘-’,
所以我们要求的就是找出在区间[3,n],那些数可以拼出s-a[2] (因为a[2]前面是‘-’已经确定下来了)
那么接下来 一个01背包就可以解决了,我们就找出了前面符号为负号的数,其他的就必然是正号。
输出
其实我的输出是看题解的,
那我就用我的理解来解释一下 其他题解的输出方式是正确的
很显然输出方案不止一种,我们只要找一种就行了。
因为 负负得正 这个运算法则 让我们难确定执行到某一步时每个数前面的符号。
那就只好用一种方法让符号变得确定
由于 负负得正 每一个前面的符号为正的数都要被减偶数次,
现在我们再把这个偶数次变得再具体一点,要么被减0次要么2次.
显然a[1]必定是被减0次,其他的前面符号为正的数都是被减2次。
一次来自 a[i-1]-a[i] ,另一次来自 a[1]-(a[i-1]-a[i])
`
````
#include<bits/stdc++.h>
using namespace std;
int n,t;
int a[10001],f[100001],book[10001];
int flag;
void find(int x,int s){
if(x==0){
flag=1;
return ;
}
for(int i=s;i>=3;i--){
if(x-a[i]>=0&&f[x-a[i]]){
book[i]=1;
find(x-a[i],i-1);
if(flag) return ;
book[i]=0;
}
}
}
int main(){
int sum=0;
cin>>n>>t;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
int s=(sum-t>>1)-a[2];
f[0]=1;
for(int i=3;i<=n;i++)
for(int j=s;j>=a[i];j--)
f[j]=f[j]|f[j-a[i]];
book[2]=1;
find(s,n);
int cnt=0;
for(int i=2;i<=n;i++){
if(!book[i]){
cout<<i-cnt-1<<endl;
cnt++;
}
}
for(int i=2;i<=n;i++)
if(book[i])
cout<<1<<endl;
return 0;
}````
为什么[3-n]随便assign +-都能和一个方案对应
最好的解释!就只有你的我能看懂!
book数组表示的意思是?
这里的book数组其实相当于一个bool数组,用来标记那些前面有负号的数字的,find函数的作用就是将其中一组解求出来
非常感谢!这道题我已经按自己的思路整理在洛谷博客上了,还请您过目
https://www.luogu.com.cn/blog/wqqakioi/tai-dan-fen-xi-yong-gan-di-qu-ba-ta-chou-xiang-cheng-mu-xing