3902-luogu 最长不下降子区间

阅读量：5254 次

发布时间：2019-06-14

本文共 1348 字，大约阅读时间需要 4 分钟。

题目

现有数列A1,A2,…An ，修改最少的数字，使得数列严格单调递增。

依旧是书上的题

但是书上的范围比较小

而

lg上的数据范围很大

按书上的

方法

是会超时只能过一半的数据

但是

算法思路还算可以

所以还是分析一下吧

#include<cstdio>

using namespace std;

int n,l;

int a[100000][3];

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i][1]);

a[i][2]=1; //每一个数自身就是一个长度为一的最长不下降子序列

}

for(int i=n-1;i>=1;i--)

{

l=0;

for(int j=i+1;j<=n;j++)

if(a[j][1]>a[i][1] && a[j][2]>l) //当a[i]后面的数大于前面的数的时候

l=a[j][2];//如果后面有比当前还大的最长子序列就替换否则不替换

if(l>0)

a[i][2]=l+1;//当后面的一直都是下降的时候也就是前面循环中的if一直不成立 l必定为0 那么这个就不成立了

}//从后往前判断每个点到最后的最长不下降子序列

int k=l;

for(int j=1;j<=n;j++)

if(a[j][2]>a[k][2])

k=j;

printf("%d",n-a[k][2]);//寻找最大子序列并输出最少替换

return 0;

}

那么

就下来

就是

较优解了

/*题解

相当于找出最长上升子序列，然后要修改的数字数即数列长度减最长上升子序列长度

但是这个最长上升子序列需要优化

有一个经典的二分优化最长上升子序列的方法设f存放一个上升序列，每次对于数列中的一个数Ai，将它与序列最后面的一个数比较，若大于最后一个数那么上身序列长度+1，否则二分在上升序列中找一个刚好比它大的数，用Ai代替这个数，这样做不会对原有结果产生影响，因为原有结果已经固定了，且不会破坏上升序列，可以使上升序列更优，因为在不破坏严格单调递增同时让序列中的数尽可能小，就可以在序列后放更多的数了 */

#include <cstdio>

using namespace std;

int n,ans=1;//ans 累加器

int a[100005],f[100005];

int main()

{

scanf("%d",&n);

for (int i=1;i<=n;i++)

scanf("%d",&a[i]);

f[1]=a[1];

for (int i=2;i<=n;i++)

{