首页 > ACM题库 > HDU-杭电 > hdu 2712 The Cow Lineup-贪心-[解题报告]other
2014
02-14

hdu 2712 The Cow Lineup-贪心-[解题报告]other

The Cow Lineup

问题描述 :

Farmer John’s N cows (1 <= N <= 100,000) are lined up in a row.Each cow is labeled with a number in the range 1…K (1 <= K <=10,000) identifying her breed. For example, a line of 14 cows might have these breeds:

1 5 3 2 5 1 3 4 4 2 5 1 2 3

Farmer John’s acute mathematical mind notices all sorts of properties of number sequences like that above. For instance, he notices that the sequence 3 4 1 3 is a subsequence (not necessarily contiguous) of the sequence of breed IDs above. FJ is curious what is the length of the shortest possible sequence he can construct out of numbers in the range 1..K that is NOT a subsequence of the breed IDs of his cows. Help him solve this problem.

输入:

* Line 1: Two integers, N and K

* Lines 2..N+1: Each line contains a single integer that is the breed ID of a cow. Line 2 describes cow 1; line 3 describes cow 2; and so on.

输出:

* Line 1: Two integers, N and K

* Lines 2..N+1: Each line contains a single integer that is the breed ID of a cow. Line 2 describes cow 1; line 3 describes cow 2; and so on.

样例输入:

14 5
1
5
3
2
5
1
3
4
4
2
5
1
2
3

样例输出:

3

Hint
All the single digit 'sequences' appear. Each of the 25 two digit sequences also appears. Of the three digit sequences, the sequence 2, 2, 4 does not appear.

开始的时候没有想出算法,上网查题解,居然有人说这题是动态规划……无奈。偶然间看到了上海交大马融牛的解题表格:只有一句话,从前向后扫描。才知道这道题用到的只不过是一个贪心思想。

贪心思想:

把序列划分成尽量多的连续子序列,使得每一个连续子序列都满足如下条件:

1..k每个数字都在这个子序列中出现过一次,并且至少有一个数字只出现过一次。

这样的子序列的个数+1就是答案

贪心思想证明:

要让长度为j的序列全部出现,必须满足第一个数字可以取1..k任意一个,第二个数字可以取1..k任意一个……以此类推

当已经划分成j个子序列并无法向后划分的时候,说明第j+1个数是不能在1..k的范围内自由选择的。所以,最短不出现子序列的长度是k+1.

证毕。

CODE

program POJ1989;//by_poetshy
 const
     maxn=100000;
 var
     a                        :array[1..maxn]of longint;
     v                        :array[1..maxn]of boolean;
     i,n,k,j                    :longint;
     ans                        :longint;
 
 begin
     readln(n,k);
     for i:=1 to n do readln(a[i]);
     j:=0;
     fillchar(v,sizeof(v),0);
     for i:=1 to n do
         begin
             if not v[a[i]] then
                 begin    
                     v[a[i]]:=true;
                     inc(j);
                 end;
             if j=k then
                 begin
                     fillchar(v,sizeof(v),0);
                     j:=0;inc(ans);
                 end;
         end;
     writeln(ans+1);
 end.

解题转自:http://www.cnblogs.com/Thispoet/archive/2011/08/31/2160775.html