Description
若对于除首尾位置之外的元素，每一个位置要么比两侧相邻的数字小，要么比两侧相邻的数字大，则称这样的数组为波浪数组
现在有一个长度为 \(n\) 的数组，你每次操作可以将任意一个位置的数字修改成任意一个新数字。
求将其变成一个波浪数组所需的最小修改次数
Solution
首先，对于一个合法的波浪数组一定是波峰波谷交替出现
我们在修改一个值时，我们关注的是相对位置
具体我们将之改为多少是没有那么重要的
我们可以将波峰都看做inf，波谷都看做-inf
而我们每一次修改都可以看做将i节点从波峰改为波谷或波谷改为波峰
考虑动态规划
我们定义 \(f[i][0/1][0/1]\) 为扫描到数组的 \(i\) 位置，且此位置是波谷／波峰，此位置没改动／改动过所需要的最小修改次数。
详细点说就是
第一维表示看到第 \(i\) 位
第二维表示 修改/不修改 后第 \(i\) 位是波峰还是波谷，\(0\) 为波谷，\(1\) 为波峰
第三维表示第 \(i\) 位是否进行了修改，\(0\) 表示未修改，\(1\) 表示修改
考场上定义的状态是两维的，但是后来发现只记录大小关系是不行的，因为有可能通过改变而修改了这个数字和前一个数字的大小关系。只记录是否改变过也不行，因为不知道上一个数字和之前的大小关系，就无法确定这个数字应该改得更大还是更小。
我们最终的答案就是 \(min\{f[n][0][0],f[n][0][1],f[n][1][0],f[n][1][1]\}\)
知道状态之后，我们进行分类讨论：
-
\(a[i]>a[i-1]\)
-
\(a[i]<a[i-1]\)
-
\(a[i]=a[i-1]\)
讨论这三种不同的情况即可得到答案。
这里以 \(a[i]>a[i-1]\) 时的情况为例详细说明一下转移的过程
- 若第 \(i\) 位是波峰且未修改第 \(i\) 位，那么第 \(i-1\) 位就是波谷，因为 \(a[i]>a[i-1]\)，所以第 \(i-1\) 位是否修改了都符合条件，所以取两者中的较小值，即
- 若第 \(i\) 位是波峰且修改了第 \(i\) 位，那么第 \(i-1\) 位就是波谷，因为 \(a[i]>a[i-1]\)，所以第 \(i-1\) 位是否修改了都符合条件，所以取两者中的较小值，又因为我们是修改后第 \(i\) 位成为波峰，所以要加 \(1\)，即
或
\[f[i][1][1]=f[i][1][0]+1 \]- 若第 \(i\) 位是波谷且未修改第 \(i\) 位，那么第 \(i-1\) 位就是波峰，因为 \(a[i]>a[i-1]\) 且未修改，所以我们只有当第 \(i-1\) 位已修改为波峰才符合条件，即
- 若第 \(i\) 位是波谷且修改了第 \(i\) 位，那么第 \(i-1\) 位就是波峰，因为 \(a[i]>a[i-1]\) 且我们进行了修改，所以第 \(i-1\) 位是否修改了都符合条件，所以取两者中的较小值，又因为我们是修改后第 \(i\) 位成为波谷，所以要加 \(1\)，即
其他两种情况大同小异，推理一下即可。
完整代码:
#include<bits/stdc++.h>
using namespace std;
int a[100010],n,ans;
int f[100010][2][2];
//第一维表示看到第i位
//第二维表示 修改/不修改 后第i位是波峰还是波谷，0为波谷，1为波峰
//第三维表示第i位是否进行了修改，0表示未修改，1表示修改
int getmin(int x){
return min(min(min(f[x][0][0],f[x][0][1]),f[x][1][0]),f[x][1][1]);
}
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);
}
f[1][1][1]=f[1][0][1]=1;
for(int i=2;i<=n;i++){
if(a[i]>a[i-1]){
f[i][1][0]=min(f[i-1][0][1],f[i-1][0][0]);
f[i][1][1]=f[i][1][0]+1;
f[i][0][0]=f[i-1][1][1];
f[i][0][1]=min(f[i-1][1][1],f[i-1][1][0])+1;
}else if(a[i]<a[i-1]){
f[i][1][0]=f[i-1][0][1];
f[i][1][1]=min(f[i-1][0][0],f[i-1][0][1])+1;
f[i][0][0]=min(f[i-1][1][0],f[i-1][1][1]);
f[i][0][1]=f[i][0][0]+1;
}else{
f[i][1][0]=f[i-1][0][1];
f[i][1][1]=min(f[i-1][0][0],f[i-1][0][1])+1;
f[i][0][0]=f[i-1][1][1];
f[i][0][1]=min(f[i-1][1][0],f[i-1][1][1])+1;
}
}
ans=getmin(n);
cout<<ans;
return 0;
}