主要给自己看,做一个记录
给定一个整数数组 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
题目: 减操作
看了题解,思路是先求出所有符号为负的和S,然后记录下来在当前和Si情况下,能由哪些a[i]组成(这部分需要用到动态规划来得到是否能从另一个和是否满足Si = Sj + a[i]的情况,且能转移过来,能就说明当前和是可以由当前序列得到的),那么接下来就是得到方案的序列了,这时候用到动态规划得到的“当前和是否能由a[i]组成”,我们可以dfs找到如果选择当前和为S,且选择a[i]的情况是否为一种解,如果为一种解,那么这个序列就是答案,否则就会继续寻找合适的a[i]跟和S。当前面符号为负的a[i]被找出来之后,那么剩下的都是为符号为正,正号的a[i]可以先让a[i-1]进行一次减操作,然后最后在被a[1]进行减操作,这样就会变成正好,于是可以记录下来其当前的位置为 i - cnt - 1(这里cnt为减操作的次数,例如1 2 3 4序列,可以con(2),那么cnt+1=1,序列变1 -1 4,此时我们想要操作4的位置,那就变成了4-1-1=2的位置,变成1 -5),然后剩下的符号位置全都可以由con(1)得到,所以剩下的只需打印 1 即可
#include<iostream>
using namespace std;
const int N = 110,M = 10010;
int a[N];
bool dp[M];//设定是否能能组成和为n,能为1,不能为0。
bool st[M];
int flag;
int n,t;
void find(int s,int x)
{
if(s == 0)
{
flag = true;
return;
}
for(int i = x; i >= 3; i --)
if(s-a[i] >= 0 && dp[s-a[i]])
{
st[i] = true;
find(s-a[i],i-1);
if(flag) return;
st[i] = false;
}
}
int main()
{
cin>>n>>t;
int sum = 0;
for(int i = 1; i <= n ;i ++)
{
cin>>a[i];
sum += a[i];
}
int s = (sum-t>>1)-a[2];//剩下的前面为负号的数的和。
dp[0] = 1;
for(int i = 3; i <= n; i++)
for(int j = s; j >= a[i]; j --)
dp[j] |= dp[j-a[i]];//是否能由j-a[i]转移过来组成和为j;
st[2] = true;
find(s,n);
int cnt = 0;
for(int i = 2; i <= n; i ++)
if(!st[i])
{
cout<<i-cnt-1<<endl;
cnt++;
}
for(int i = 2; i <= n; i ++)
if(st[i]) cout<<1<<endl;
return 0;
}