BZOJ 1609 [Usaco2008 Feb]Eating Together麻煩的聚餐：LIS LDS (nlogn)

題目鏈接：http://www.lydsy.com/JudgeOnline/problem.php?id=1609

題意：

　　給你一個只由數字"1,2,3"組成的序列a[i]，共n個數。

　　你可以任意更改這些數字，使得序列中每一種數字都“站在一起”，并且單調不減或不增。

　　例如："1111222", "332211"...

　　問你至少更改多少個數字。

題解：

　　單調不減：求原序列LIS（最長非降子序列），當前答案t1 = n - LIS.

　　單調不增：求原序列LDS（最長非升子序列），當前答案t2 = n - LDS.

　　最終答案ans = min(t1,t2).

　　注：n為30000，求LIS & LDS用nlogn方法。

AC Code:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define MAX_N 30005
 5 
 6 using namespace std;
 7 
 8 int n;
 9 int a[MAX_N];
10 int d[MAX_N];
11 
12 int cal_lis()
13 {
14     int len=1;
15     d[1]=a[0];
16     for(int i=1;i<n;i++)
17     {
18         if(a[i]>=d[len])
19         {
20             d[++len]=a[i];
21             continue;
22         }
23         int lef=1;
24         int rig=len;
25         while(rig-lef>1)
26         {
27             int mid=(lef+rig)/2;
28             if(a[i]>=d[mid]) lef=mid;
29             else rig=mid;
30         }
31         int ans;
32         if(a[i]<d[lef]) ans=0;
33         else ans=lef;
34         d[ans+1]=min(d[ans+1],a[i]);
35     }
36     return len;
37 }
38 
39 int cal_lds()
40 {
41     int len=1;
42     d[1]=a[0];
43     for(int i=1;i<n;i++)
44     {
45         if(a[i]<=d[len])
46         {
47             d[++len]=a[i];
48             continue;
49         }
50         int lef=1;
51         int rig=len;
52         while(rig-lef>1)
53         {
54             int mid=(lef+rig)/2;
55             if(a[i]<=d[mid]) lef=mid;
56             else rig=mid;
57         }
58         int ans;
59         if(a[i]>d[lef]) ans=0;
60         else ans=lef;
61         d[ans+1]=max(d[ans+1],a[i]);
62     }
63     return len;
64 }
65 
66 int main()
67 {
68     cin>>n;
69     for(int i=0;i<n;i++)
70     {
71         cin>>a[i];
72     }
73     int v1=cal_lis();
74     int v2=cal_lds();
75     cout<<n-max(v1,v2)<<endl;
76 }

轉載于:https://www.cnblogs.com/Leohh/p/7604687.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/253282.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/253282.shtml
英文地址，請注明出處：http://en.pswp.cn/news/253282.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！