杨家坪网站建设,红豆网梧州论坛,一键优化在哪里打开,网站平台建设调研报告题目链接#xff1a;http://www.lydsy.com/JudgeOnline/problem.php?id1609 题意#xff1a; 给你一个只由数字1,2,3组成的序列a[i]#xff0c;共n个数。 你可以任意更改这些数字#xff0c;使得序列中每一种数字都“站在一起”#xff0c;并且单调不减或不增…题目链接http://www.lydsy.com/JudgeOnline/problem.php?id1609 题意 给你一个只由数字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 iostream2 #include stdio.h3 #include string.h4 #define MAX_N 300055 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 len1;
15 d[1]a[0];
16 for(int i1;in;i)
17 {
18 if(a[i]d[len])
19 {
20 d[len]a[i];
21 continue;
22 }
23 int lef1;
24 int riglen;
25 while(rig-lef1)
26 {
27 int mid(lefrig)/2;
28 if(a[i]d[mid]) lefmid;
29 else rigmid;
30 }
31 int ans;
32 if(a[i]d[lef]) ans0;
33 else anslef;
34 d[ans1]min(d[ans1],a[i]);
35 }
36 return len;
37 }
38
39 int cal_lds()
40 {
41 int len1;
42 d[1]a[0];
43 for(int i1;in;i)
44 {
45 if(a[i]d[len])
46 {
47 d[len]a[i];
48 continue;
49 }
50 int lef1;
51 int riglen;
52 while(rig-lef1)
53 {
54 int mid(lefrig)/2;
55 if(a[i]d[mid]) lefmid;
56 else rigmid;
57 }
58 int ans;
59 if(a[i]d[lef]) ans0;
60 else anslef;
61 d[ans1]max(d[ans1],a[i]);
62 }
63 return len;
64 }
65
66 int main()
67 {
68 cinn;
69 for(int i0;in;i)
70 {
71 cina[i];
72 }
73 int v1cal_lis();
74 int v2cal_lds();
75 coutn-max(v1,v2)endl;
76 } 转载于:https://www.cnblogs.com/Leohh/p/7604687.html
