专栏首页HansBug's Lab1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

1609: [Usaco2008 Feb]Eating Together麻烦的聚餐

Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1010  Solved: 606 [Submit][Status]

Description

为了避免餐厅过分拥挤,FJ要求奶牛们分3批就餐。每天晚饭前,奶牛们都会在餐厅前排队入内,按FJ的设想所有第3批就餐的奶牛排在队尾,队伍的前端由设定为第1批就餐的奶牛占据,中间的位置就归第2批就餐的奶牛了。由于奶牛们不理解FJ的安排,晚饭前的排队成了一个大麻烦。 第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 3)的卡片。虽然所有N(1 <= N <= 30,000)头奶牛排成了很整齐的队伍但谁都看得出来,卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后,FJ找到了一种简单些的方法:奶牛们不动,他沿着队伍从头到尾走一遍把那些他认为排错队的奶牛卡片上的编号改掉,最终得到一个他想要的每个组中的奶牛都站在一起的队列,例如111222333或者333222111。哦,你也发现了,FJ不反对一条前后颠倒的队列,那样他可以让所有奶牛向后转,然后按正常顺序进入餐厅。 你也晓得,FJ是个很懒的人。他想知道,如果他想达到目的,那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候,都不会挪位置。

Input

第1行: 1个整数:N 第2..N+1行: 第i+1行是1个整数,为第i头奶牛的用餐批次D_i

Output

第1行: 输出1个整数,为FJ最少要改几头奶牛卡片上的编号,才能让编号变成他设想中的样子

Sample Input

5

1

3

2

1

1

输入说明:

队列中共有5头奶牛,第1头以及最后2头奶牛被设定为第一批用餐,第2头奶牛的预设是第三批用餐,第3头则为第二批用餐。

Sample Output

1

输出说明:

如果FJ想把当前队列改成一个不下降序列,他至少要改2头奶牛的编号,一种可行的方案是:把队伍中2头编号不是1的奶牛的编号都改成1。不过,如果FJ选择把第1头奶牛的编号改成3就能把奶牛们的队伍改造成一个合法的不上升序列了。

HINT

Source

Silver

题解:一个比较萌的DP,用a[I,j]存储当修改到第i头牛时改为j(也可以是保持原状其实),然后直接扫一遍,接着反向来一遍,注意i=1时最好特判下

 1 var
 2    i,j,k,l,m,n:longint;
 3    a:array[0..50000,1..3] of longint;
 4    b:array[0..50000] of longint;
 5 function min(x,y:longint):longint;
 6          begin
 7               if x<y then min:=x else min:=y;
 8          end;
 9 
10 begin
11      read(n);
12      for i:=1 to n do read(b[i]);
13      for i:=1 to n do
14          begin
15               if i=1 then
16                  begin
17                       for j:=1 to 3 do
18                           if b[1]=j then a[1,j]:=0 else a[1,j]:=1;
19                  end
20               else
21                   begin
22                        for j:=1 to 3 do
23                            begin
24                                 l:=maxlongint;
25                                 for k:=1 to j do
26                                     begin
27                                          if a[i-1,k]<l then l:=a[i-1,k];
28                                     end;
29                                 if b[i]=j then a[i,j]:=l else a[i,j]:=l+1;
30                            end;
31                   end;
32 
33          end;
34      m:=(min(a[n,3],min(a[n,1],a[n,2])));
35      for i:=1 to n div 2 do
36          begin
37               l:=b[i];
38               b[i]:=b[n+1-i];
39               b[n+1-i]:=l;
40          end;
41      for i:=1 to n do
42          begin
43               if i=1 then
44                  begin
45                       for j:=1 to 3 do
46                           if b[1]=j then a[1,j]:=0 else a[1,j]:=1;
47                  end
48               else
49                   begin
50                        for j:=1 to 3 do
51                            begin
52                                 l:=maxlongint;
53                                 for k:=1 to j do
54                                     begin
55                                          if a[i-1,k]<l then l:=a[i-1,k];
56                                     end;
57                                 if b[i]=j then a[i,j]:=l else a[i,j]:=l+1;
58                            end;
59                   end;
60 
61          end;
62      m:=min(m,min(a[n,3],min(a[n,1],a[n,2])));
63      writeln(m);
64 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1601: [Usaco2008 Oct]灌水

    1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

    HansBug
  • 算法模板——计算几何2(二维凸包——Andrew算法)

    实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反...

    HansBug
  • 2818: Gcd

    2818: Gcd Time Limit: 10 Sec  Memory Limit: 256 MB Submit: 2170  Solved: 979 [Su...

    HansBug
  • 2818: Gcd

    2818: Gcd Time Limit: 10 Sec  Memory Limit: 256 MB Submit: 2170  Solved: 979 [Su...

    HansBug
  • 1218: [HNOI2003]激光炸弹

    1218: [HNOI2003]激光炸弹 Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 1139  Solv...

    HansBug
  • 2729: [HNOI2012]排队

    2729: [HNOI2012]排队 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 957  Solved:...

    HansBug
  • 【技术】从文本挖掘和机器学习中洞悉数据

    文本挖掘分析的是包含在自然语言文本中的数据。它可以帮助企业从文本型数据中获得具有潜在价值的商业洞察力,比如Word文档、邮件或Facebook、Tw...

    小莹莹
  • 【Science 封面】世界首个人工再造真核生命体问世,三分之二中国造

    【新智元导读】今天《Science》以封面专题的形式,发表 7 篇文章介绍了世界上首个人工再造的真核生命体。天津大学、清华大学和华大基因的研究人员参与了这项国际...

    新智元
  • JAVA知识点总结篇(三)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    村雨遥
  • 对物流园区建设的思考与建议

    物流业作为支撑国民经济的基础性和综合性产业,在国务院出台了调整和振兴物流业的规划政策后,更是受到企业和政府的格外关注,各级地方政府也相继出台政策措施支持区域物流...

    物流IT圈

扫码关注云+社区

领取腾讯云代金券