大意
说实话没多少关系
将一种初始状态转移到一种目标状态
求最优操作序列
常规做法
使用 或 跑出最优解出来
但这样写起来比较麻烦绝对不是我懒
另解
我们看样例 3 5 6 4 2 1 3 5 7 6 4 2 3 5 4
可以发现部分结构和变化相似或相同
于是我们做差分
差分
什么？差分是什么？ 对于差分数组 和原数组
有
众所周知 是差分的逆运算
如果你不理解，没关系，我们对于差分数组 进行前缀和运算
即
中 等于
如果不理解可以写一遍或者推一遍
从样例推规律
于是我们先做几遍差分
cin>>n;
for(int i = 1 ; i <= n * (n+2) ; i++){
cin>>num[i];
}
for(int k = 1 ; k <= 3 ; k++){
for(int i = 1 ; i <= n * (n+2) ; i++){
cout<<num[i] - num[i-1]<<" ";
}
for(int i = 1 ; i <= n * (n+2) ; i++){
num[i] = num[i] - num[i-1]
}
puts("");
}
得到三行数据
3 2 1 -2 -2 -1 2 2 2 -1 -2 -2 1 2 -1
3 -1 2 -4 2 -3 5 -3 5 -6 4 -6 7 -5 4
3 -4 6 -10 12 -15 20 -23 28 -34 38 -44 51 -56 60
发现一遍差分的时候数据比较有规律
于是我们先总结出一套规律
- 数据长度为
- 中间有 个
- 除去开头与结尾 ， 数据对称
- 除去开头与结尾数据中只有 和 且正负交替
- 开头数字为
暂时先整理这么多，先把代码码出来得到差分数组后对其进行前缀和即可
AC代码
~~什么？AC代码？~~我只有部分
临时搓的，思路较乱，但也能看，见谅
for (i = 2; i <= n * (n + 1) / 2; i++) {
ll t = i;
for (i = t; i < t + flag2; i++) {
num[i] = 2 * flag1;
}
flag1 *= -1;
flag2++;
num[i] = flag1 * -1;
}
ll t = i;
for (i = t; i < t + n; i++) {
num[i] = 2 * flag1;
}
flag1 *= -1;
flag2--;
t = i;
for (i = t; i <= n * (n + 2); i++) {
num[i++] = flag1;
ll te = i;
for (i = te; i < te + flag2; i++) {
num[i] = 2 * flag1;
}
flag1 *= -1;
flag2--;
i--;
}
相信有和这同思路但更简洁的代码