劃分數列
題目位址
Solution
考慮遞推。
設\(f_i\)表示\(a_1\sim a_i\)的最少劃分段數,\(p_i\)代表以\(i\)結尾單調不降的一段的起點,\(q_i\)則表示以\(i\)結尾單調不升的一段的起點,注意:起點代表這一段第一個數的前一個坐标。
我們可以得到以下轉移方程:
\[\large f_i=\min(f_{p_i}+1,f_{q_i}+1)
\]
也就是說對于\(a_1\sim a_i\)的分段數可以是由上一個單調不降(升)的數段加上目前這一段(指\(a_{p_i+1}\ or\ a_{q_i+1}\sim a_i\)這一段)。
- \(a_i\ge a_{i-1}\),那麼\(p_i\)的起點與上一項相同,即\(p_i=p_{i-1}\)。
- \(a_i< a_{i-1}\),那麼\(p_i\)的起點更新,\(p_i=i-1\)。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int f[N],p[N],q[N],a[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
p[i]=q[i]=i-1;
if(a[i]>=a[i-1])p[i]=p[i-1];
if(a[i]<=a[i-1])q[i]=q[i-1];
f[i]=min(f[p[i]]+1,f[q[i]]+1);
}
printf("%d",f[n]);
return 0;
}