CF713C Sonya and Problem Wihtout a Legend
前言
\(\text{O}(n^2)\) DP方法。
这一道题的重点在于离散化，网上有七八成的题解都讲的不是很清晰，所以我在这里讲一下。
upd - 2021.8.8 ： 修正笔误。
upd - 2020.7.31 ：原来的证明有一点问题，合并后的函数应该是满足严格递增的，已修改。
upd - 2021.5.21 ：修改了图床并更正原来的一处笔误，所以重新提交一次。
upd - 2021.5.22 ： 修正以前错误的排版，添加了更多的说明。
思路：
既然这是线性 DP。
从以下两个角度出发：
-
我从哪里来（当前状态可以由哪些状态得到）?
-
我到哪里去（当前状态可以推出哪几个状态）?
我们不难想到：
设 \(f[i][j]\) 表示 \(a[i]\) 变成 \(re[j]\) 所需的最小操作次数。
可 \(a[i]\) 和 \(re[j]\) 是哪里来的啊？
我们设原序列为 \(a[]\)，我们想要达到的“理想”序列为 \(re[]\)。
那么，代码如下：
for(register long long i=1;i<=n;++i){
cin>>a[i];
a[i]-=i;
re[i]=a[i];
}
sort(re+1,re+n+1);
接下来我就讲讲为什么要这样做：
为什么是 re[i]=a[i]-i 呢？
很好理解，我在这里举个例子。
（这里举的例子是 POJ3666，因为离散的方法和此题一样，所以我就以 POJ3666 作为例子讲解这题的离散化）。
先不管这道题的要求。我们先假设加一减一的操作变为了修改操作（POJ3666）。
那么先来一组数据：
\(a[]:\{1,3,2,3,5\} , (n=5)\)
如果我们想要修改它，使得它是单调不减（这里也是 POJ3666 ）的。
要怎么修改？
显然，我们的第一思路是这么修改：
\(a[]:\{1,2,3,4,5\}\)
因为这里有重复的3。
所以，我们需要更多的次数去修改它。
为了避免这种情况，我们给每个 \(a[i]\) 减去 \(i\)。
为什么呢？
因为 \(i\) 在这里一定是严格递增的（你从头往后扫，下标难道不递增？），现在看一下减去 \(i\) 之后是怎么样的：
\(re[]:\{ 0,1,-1,-1,0\}\)
现在还是有重复的，不过先不要着急。
我画一个图。
这是你的 \(re\) 序列（不下降）：
这是你的 \(i\) （所有的 \(i\) 组成的序列）
那我们将这两个序列合并，这个合并的序列一定是这样的：
其实就是一个不等式的加减。
举个例子：
\(re[]=\{ 1,2,3,3,3\}\)
\(i[]=\{1,2,3,4,5\}\)
合并之后：
\(2,4,6,7,8\)，是不是满足严格递增？
好的，这里可能会有一点绕。
我们再重新看一看:
\(re[]:\{ 0,1,-1,-1,0\}\)
现在我们只需要使这一个 \(re\) 中不下降的元素尽量多，那么我们需要修改的次数就会尽量的少（最优）。
（也就是要求一个最长不下降子序列再减去元素个数）。
好了，把这一个离散的思路放到我们这一题，只需要改一下条件就可以啦。
（没听懂自行返回再来几遍，我讲的已经比较清晰了）。
现在离散化已经搞定了。那么是时候看方程了。
根据状态的定义，\(f[i][j]\) 只可能从 \(f[i-1][j]\) 转移过来。
那么我们转移过后（也就是修改一次）的代价就是 \(|a[i]-re[j]|\)。
（这里是加一减一，所以代价是它们的差的绝对值）。
然后为了最优，我们记录一下这一层之前的“最优”，拿来和现在的“决策”比较一下就行（代码里的 minv）。
方程：
\[\begin{cases}minv=\min(minv,f[i-1][j])\\f[i][j]=minv+|a[i]-re[j]|\end{cases} \]（最开始的时候 \(minv\) 要赋值为一个超级大的值）。
很好，到这里这道题就基本完成了，如果没有听懂的同学请从头再多看几遍。
AC记录
下面给出代码实现（数据大所以用long long）：
#include
using namespace std;
long long f[3001][3001];//f[i][j]表示a[i]变为re[j]时的最小操作次数
long long n;
long long a[3001];//原序列
long long re[3001];//目标序列
long long minn,res=2e18;//这里要赋很大的值，否则以CF的毒瘤数据你会WA。
long long abs_ll(long long a){
return a>=0?a:-a;
}
namespace Accepted{
void zjk_ak_ioi(){
cout<>n;
for(register long long i=1;i<=n;++i){
cin>>a[i];
a[i]-=i;
re[i]=a[i];//离散化
}
sort(re+1,re+n+1);//排一遍，使目标序列严格递增
for(register long long i=1;i<=n;++i){
f[1][i]=abs_ll(a[1]-re[i]);//给f一个初值，这里是预处理
}
for(register long long i=2;i<=n;++i){
minn=2e18;//这里每一次都要赋值，否则会错（因为每次操作都要用，也就是每一层都有不同的情况）
for(register long long j=1;j<=n;++j){
minn=min(minn,f[i-1][j]);
f[i][j]=minn+abs_ll(a[i]-re[j]);//转移
}
}
for(register int i=1;i<=n;++i){
res=min(res,f[n][i]);//从整个序列的情况去找最小值
}
Accepted::zjk_ak_ioi();//喊出zjkAKIOI，借用神的力量，让我AC！
}
代码里那个奇怪的函数不用管啦（个人习惯），你只需要直接输出 res 就好了。
一些类似的变式：
-
Poj3666 - Making the Grade
-
LuoguP2501 - [HAOI2006]数字序列