最长上升子序列的变形（N*log（N））hdu5256

序列变换

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 820 Accepted Submission(s): 336

Problem Description

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

Input

第一行输入一个

Output

对于每组数据，先输出一行

Case #i:

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

Sample Input

1 10

2 5 4

Sample Output

Case #1:

Case #2:

分析：找出的最长上升子序列a[i]-a[j]>=i-j；把a[i]-=i;之后的值按照非严格递增最长子序列的值L，最后n-L就是要改变的最小值

程序：

 1 #include"stdio.h"
 2 #include"string.h"
 3 #include"stdlib.h"
 4 #include"algorithm"
 5 #include"queue"
 6 #include"math.h"
 7 #include"iostream"
 8 #include"vector"
 9 #define M 100009
10 #define inf 0x3f3f3f3f
11 #define eps 1e-9
12 #define PI acos(-1.0)
13 #include"map"
14 #include"vector"
15 #include"set"
16 #include"string"
17 #include"stack"
18 #define LL __int64
19 using namespace std;
20 int a[M],b[M],c[M];
21 int finde(int n,int k)
22 {
23     int l=1;
24     int r=n;
25     while(l<=r)
26     {
27         int mid=(l+r)/2;
28         if(c[mid]<=k)
29             l=mid+1;
30         else
31             r=mid-1;
32     }
33     return l;
34 }
35 int main()
36 {
37     int n;
38     int T,kk=1;
39     cin>>T;
40     while(T--)
41     {
42         scanf("%d",&n);
43         for(int i=1;i<=n;i++)
44         {
45             scanf("%d",&a[i]);
46             a[i]-=i;
47         }
48 
49         memset(c,inf,sizeof(c));
50         b[1]=1;
51         c[1]=a[1];
52         for(int i=2;i<=n;i++)
53         {
54             int id=finde(n,a[i]);
55             b[i]=id;
56             c[id]=a[i];
57         }
58         printf("Case #%d:
",kk++);
59         int maxi=0;
60         for(int i=1;i<=n;i++)
61             maxi=max(maxi,b[i]);
62         printf("%d
",n-maxi);
63     }
64     return 0;
65 }

View Code

 1 #include"stdio.h"
 2 #include"string.h"
 3 #include"stdlib.h"
 4 #include"algorithm"
 5 #include"queue"
 6 #include"math.h"
 7 #include"iostream"
 8 #include"vector"
 9 #define M 100009
10 #define inf 0x3f3f3f3f
11 #define eps 1e-9
12 #define PI acos(-1.0)
13 #include"map"
14 #include"vector"
15 #include"set"
16 #include"string"
17 #include"stack"
18 #define LL __int64
19 using namespace std;
20 int a[M],b[M],n;
21 int finde()
22 {
23     int t=0;
24     b[t]=a[1];
25     t++;
26     for(int i=2;i<=n;i++)
27     {
28         int id=upper_bound(b,b+t,a[i])-b;
29         if(id==t)
30             t++;
31         b[id]=a[i];
32     }
33     return t;
34 }
35 int main()
36 {
37     int T,kk=1;
38     cin>>T;
39     while(T--)
40     {
41         scanf("%d",&n);
42         for(int i=1;i<=n;i++)
43         {
44             scanf("%d",&a[i]);
45             a[i]-=i;
46         }
47         int leng=finde();
48         printf("Case #%d:
%d
",kk++,n-leng);
49 
50     }
51 }

View Code