题目描述
给定一个整数数组(a_1,a_2,…,a_n)。
定义数组第 i 位上的减操作：把(a_i)和(a_{i+1})换成(a_i - a_{i+1})。
用con(a,i)表示减操作，可以表示为：
长度为 n 的数组，经过 n-1 次减操作后，就可以得到一个整数t。
例如数组[12,10,4,3,5]经过如下操作可得到整数4：
现在给定数组以及目标整数，求完整操作过程。
输入格式
第1行包含两个整数n和t。
第2..n+1行：第i行包含数组中的第 i 个整数(a_i)。
输出格式
输出共n-1行，每行包含一个整数，第 i 行的整数表示第 i 次减操作的操作位置。
数据范围
输入样例：
5 4
12
10
4
3
5
输出样例：
2
3
2
1
解题报告
题意理解
就是说,有一种操作,名为减操作,可以将合并相邻的两个数,比如说原来的数字是.
也就是,
思路解析
性质分析
我们发现,每一次减操作都会使得序列长度减少一个.
所以说,我们发现其实对于序列的最终结果(t),可以变成这种形式.
举个例子表示一下
我们发现
对于
因为我们发现,(1)的前面没有数,可以去进行减操作.
最后一次执行的必然是(cut(1))操作
(a[1])表示,我真的想要减操作,但是我就是没有数可以和我一起减操作.
然后我们再来康康为什么一定是
其实道理和之前一样,
最后一次执行的必然是(cut(1))操作.
(a[2])表示,我真的是被迫的,(cut(1))使得(a[1]-a[2]).
状态设置
这样我们将题目转换成了
一个数列,对于数组中的数，将一些正整数变为负数，使整个数组的和为t，最后输出将哪些数变为负数.
我们发现这道题目的数据范围
数据范围真的好小啊,开一个(n*t)的数据范围丝毫没有问题.
所以说我们不妨这么设置一个状态数组.
不过我们要注意一下,C++负数下标有可能性挂掉了,所以我们不得不让所有下标加上一个固定的大数字,保证最后的下标是一个正数.
此时最大的问题就是,如何反推出我们的cut操作?
反推路径
- 为什么有些数可以是正数?也就是前面是+号?
这是一个非常重要的问题,我们发现.
假如说我们第(i)位不进行(cut)操作,那么它前面一定不是(+)号.
一个数,前面不是加号,就是减号.
只有当(i-1)位进行(cut)操作的时候,这个第(i)位才可以是减号.
这就让我们证明了.
所以找到每一个(+)号的位置,然后输出当前位置.
不过你要注意一下,输出应该是.
代码解析
#include<bits/stdc++.h>
using namespace std;
#define init() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//读入优化
const int maxn=105,maxt=20086,hh=10000;//hh是我们的下标转移常数
int n,t,f[maxn][maxt],a[maxn],ans[maxn];
void dp()
{
f[1][a[1]+hh] = 1;//a[1]必然是正数
f[2][a[1]-a[2]+hh]=-1;//a[2]必然是
for(int i=3; i<=n; i++)
for(int j=-10000+hh; j<=10000+hh; j++)
{
if(f[i-1][j])//可以转移
{
f[i][a[i]+j]=1;//+号
f[i][j-a[i]]=-1;//-号
}
}
}
void out()
{
int s=hh+t;
for(int i=n; i>=2; i--)//回溯走路径,确定+,-号
{
ans[i]=f[i][s];
if(ans[i]==1)
s-=a[i];
else if(ans[i]==-1)
s+=a[i];
}
int cnt=0;
for(int i=2; i<=n; i++)
if(ans[i]==1)//是时候减操作了.
{
cout<<i-cnt-1<<endl;
cnt++;
}
for(int i=2; i<=n; i++)
if(ans[i]==-1)//寻找
cout<<1<<endl;
}
int main()
{
init();
cin>>n>>t;
for(int i=1; i<=n; i++)
cin>>a[i];
dp();
out();
return 0;
}