2015百度之星初赛2 1005 序列变换（LIS变形）-白红宇

2015百度之星初赛2 1005 序列变换（LIS变形）

阅读量：6115 次

发布时间：2019-06-21

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

LIS(非严格)：首先我想到了LIS。然而总认为有点不正确；每一个数先减去它的下标。防止以下的情况发生：(转载) 3         增加序列是1,2,2,2,3,这样求上升子序列是3。也就是要改动2个，可是中间的两个2，变化范围又不能超过（1,3） 4         那么这样求的也就不正确，可是减掉之后。相当于给中间反复的数留下了改动的空间 5         解释下为什么能够减而保持正确性：由于题目所求时严格递增，如果是2。3, 4。那么变成1, 1, 1，所以在LIS里非严格递增就能够了 6         这也是为什么要在upper_bound的位置插入 7     另外：lower_bound返回第一个>=key的位置；upper_bound返回第一个>key的位置，这样相减才是key的个数

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int INF = 9999990;int a[100001],dp[100001];int main(){    #ifdef xxz    freopen("in.txt","r",stdin);    #endif // xxz    int n,T;    scanf("%d",&T);    for(int ca = 1; ca <= T; ca++){        scanf("%d",&n);        for(int i = 0; i < n; i++) scanf("%d",a+i),a[i] -= i;        fill(dp,dp + n, INF);        for(int i = 0; i < n; i++){            *upper_bound(dp,dp+n,a[i]) = a[i];        }        printf("Case #%d:\n%d\n",ca,n - (lower_bound(dp,dp+n,INF) - dp));    }    return 0;}