CF580A Kefa and First Steps

· · 个人记录

传送门

一、题目大意

**二、大体思路** $\ \ \ \ \ \ \ $因为题目中要求的是子段，所以这就告诉我们，我们的最长不下降序列必须是连续的，那么我们可以用一个$f$数组来存储我们的答案，用$a$数组存储我们输入的数据。我们考虑每一个数它本身即为一个子段，所以$f$数组初始化全部为$1$。 $\ \ \ \ \ \ \ $循环从$2$开始，我们查看相邻的两个数的值，如果$a_i \geq a_{i-1}$ 显然这是满足题意的，所以我们就要看看是在$f_{i-1}$的基础上$+1$还是以$f_i$来结尾，这样我们就有了状态转移方程 $f_i=max(f_{i-1}+1\ ,\ f_i)

接下来就是AC代码。

\mathcal{AC\ node} 
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define N 100050
int a[N],f[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) f[i]=1;
    for(int i=2;i<=n;i++)
        if(a[i]>=a[i-1]) f[i]=max(f[i-1]+1,f[i]);
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,f[i]);
    cout<<ans<<endl;
    return 0;
}//正推