求最长上升子序列和最长非下降子序列

先放题：HDU 5256 http://acm.hdu.edu.cn/showproblem.php?pid=5256

序列变换

我们有一个数列A1,A2...An，你现在要求修改数量最少的元素，使得这个数列严格递增。其中无论是修改前还是修改后，每个元素都必须是整数。
请输出最少需要修改多少个元素。

Input 第一行输入一个 $T (1 \leq T \leq 10)$ $T (1 \leq T \leq 10)$

$T (1 \leq T \leq 10)$

$T (1 \leq T \leq 10)$ $T (1 \leq T \leq 10)$

$T (1 \leq T \leq 10)$ $T (1 \leq T \leq 10)$

$T (1 \leq T \leq 10)$ Output对于每组数据，先输出一行
Case #%d:

然后输出最少需要修改多少个元素;

output:

Case #1:
0
Case #2:
1

  该题思路：构造序列B[i]=A[i]-i;答案为序列总长度减去B的最长不下降子序列的长度；
这题要求最长不下降子序列；
刚开始写错了。。后来网上看到了一个nlog n的做法

//最长不下降子序列nlogn  Song 

#include<cstdio>
#include<algorithm>
using namespace std;

int a[40005];
in
    t d[40005];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    if (n==0)  //0个元素特判一下 
    {
        printf("0
");
        return 0;
    }
    d[1]=a[1];  //初始化 
    int len=1;
    for (int i=2;i<=n;i++)
    {
        if (a[i]>=d[len]) d[++len]=a[i];  //如果可以接在len后面就接上，如果是最长上升子序列，这里变成> 
        else  //否则就找一个最该替换的替换掉 
        {
            int j=upper_bound(d+1,d+len+1,a[i])-d;  //找到第一个大于它的d的下标，如果是最长上升子序列，这里变成lower_bound 
            d[j]=a[i]; 
        }
       }
    printf("%d
",len);    
    return 0;
}

（里面求最长上升子序列的也标注了）

还有个n²的做法，应该只能处理少数数据

#include<cstdio>
#include<iostream>
using namespace std;
int num,n,a[1001],sum[1001];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
      {
          scanf("%d",&a[i]);
          sum[i]=1;
          for (int j=1;j<i;j++)
            if (a[j]<a[i]&&sum[j]>=sum[i])//如果a[j]比a[i]小并且第j个数的不下降序列比当前的长或相等
              sum[i]=sum[j]+1;
          num=max(num,sum[i]);//判断当前段是否为最优
      }
    printf("%d",num);
}

然后是题目ac的代码：

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxen=100010;
int T,n,a[maxen],b[maxen],dp[maxen];
int main(void){
    int t=1;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            b[i]=a[i]-i;
        }
        int len=1;
        dp[1]=b[1];
        for(int i=2;i<=n;++i){
            if(dp[len]<=b[i]){
                dp[++len]=b[i];
            }
            else{
                int j=upper_bound(dp+1,dp+1+len,b[i])-dp;   //寻找最长非下降子序列 
                dp[j]=b[i];
            }
        }
        printf("Case #%d:
",t);
        printf("%d
",n-len);
        t++;
    }
    return 0;

今天又学了这两个方法~ヾ(◍°∇°◍)ﾉﾞ 
                                                                                                                              2019.3.5
                                                                                                                              --九点了肚子还是好饱的猴