新博客,各位看官要不关注一下

导言

线性DP是动态规划的入门学习知识点,是我们入门动态规划的必备思维.

第一题

原题连接

题目描述

给定一个整数数组$a_1,a_2,…,a_n$。

定义数组第 i 位上的减操作：把$a_i$和$a_{i+1}$换成$a_i - a_{i+1}$。

用con(a,i)表示减操作，可以表示为：
$$ con(a,i)=[a_1,a_2,…,a_{i-1},a_i-a_{i+1},a_{i+2},…,a_n] $$
长度为 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 个整数$a_i$。

输出格式

输出共n-1行，每行包含一个整数，第 i 行的整数表示第 i 次减操作的操作位置。

数据范围

$$ 1 \le n \le 100 \\\\ -10000 \le t \le 10000 \\\\ 1 \le a_i \le 100 \\\\ $$

输入样例：

5 4
12
10
4
3
5

输出样例：

2
3
2
1

解题报告

题意理解

就是说,有一种操作,名为减操作,可以将合并相邻的两个数,比如说原来的数字是.
$$ 3,4,那么合并后变成-1 $$
也就是,
$$ 合并后的数字=前面一个数字-后面一个数字. \\\\ a[i]=a[i]-a[i-1] \\\\ 然后删除a[i+1] \\\\ $$

思路解析

性质分析

我们发现,每一次减操作都会使得序列长度减少一个.
$$ 即原本长度len,然后一次减操作后就会变成len-1 $$
所以说,我们发现其实对于序列的最终结果$t$,可以变成这种形式.
$$ a[1]-a[2] \pm a[3] \pm a[4] \pm a[5]=t $$
举个例子表示一下
$$ a[1] \quad a[2] \quad a[3] \quad a[4] \quad a[5] \qquad 原序列\\\\ a[1] \quad a[2]-a[3] \quad a[4] \quad [5] \qquad 此时cut(2) \\\\ a[1] \quad a[2]-a[3] \quad a[4]-a[5] \qquad 此时cut(3) \\\\ a[1] \quad a[2]-a[3]-(a[4]-a[5]) \qquad 此时cut(2) \\\\ a[1]-(a[2]-a[3]-(a[4]-a[5])) \qquad 最后cut(1) \\\\ a[1]-a[2]+a[3]+a[4]-a[5] \qquad 处理后的答案序列 $$
我们发现
$$ a[1]必须是+号,a[2]必须是-号 $$
对于
$$ a[1]必须是+号 $$
因为我们发现,$1$的前面没有数,可以去进行减操作.

最后一次执行的必然是$cut(1)$操作

$a[1]$表示,我真的想要减操作,但是我就是没有数可以和我一起减操作.

然后我们再来康康为什么一定是
$$ a[2]必须为-号 $$
其实道理和之前一样,

最后一次执行的必然是$cut(1)$操作.

$a[2]$表示,我真的是被迫的,$cut(1)$使得$a[1]-a[2]$.

状态设置

这样我们将题目转换成了
一个数列,对于数组中的数，将一些正整数变为负数，使整个数组的和为t，最后输出将哪些数变为负数.

我们发现这道题目的数据范围
$$ n \le 100 \\\\ -10000 \le t \le 10000 \\\\ $$
数据范围真的好小啊,开一个$n*t$的数据范围丝毫没有问题.

所以说我们不妨这么设置一个状态数组.
$$ f[i][cnt] \quad 表示前i个数字的和为cnt \\\\ f[i][cnt]=1 \quad 表示第i个数前面是+号 \\\\ f[i][cnt]=-1 \quad 表示第i个数前面是-号 \\\\ $$
不过我们要注意一下,C++负数下标有可能性挂掉了,所以我们不得不让所有下标加上一个固定的大数字,保证最后的下标是一个正数.

此时最大的问题就是,如何反推出我们的cut操作?

反推路径

1. 为什么有些数可以是正数?也就是前面是+号?

这是一个非常重要的问题,我们发现.
$$ 一个数字前面是+号,只有在它这一位进行cut操作. $$
假如说我们第$i$位不进行$cut$操作,那么它前面一定不是$+$号.

一个数,前面不是加号,就是减号.
$$ cut(i) \qquad a[i]-a[i+1] \\\\ cut(i-1) \qquad a[i-1]-a[i] \\\\ $$
只有当$i-1$位进行$cut$操作的时候,这个第$i$位才可以是减号.

这就让我们证明了.
$$ 一个数字前面是+号,只有在它这一位进行cut操作. $$
所以找到每一个$+$号的位置,然后输出当前位置.

不过你要注意一下,输出应该是.
$$ i-tot-1 \\\\ tot表示为当前有几个cut操作了 \\\\ $$

代码解析

#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;
}