poj-1989

//144K  141MS   C++#include <cstdio>#include <cstring>using namespace std;int K;int N;const int MAX = 10001;char flag[MAX];int completeCollectionNum = 0;int main() {    while(scanf("%d %d", &N, &K) != EOF) {        memset(flag, 0, sizeof(flag));        int unAppearNum = K;        for (int i = 1; i <= N; i++) {            int val;            scanf("%d", &val);            if (flag[val]) {            } else {                flag[val] = 1;                unAppearNum--;                if (unAppearNum == 0) {                    completeCollectionNum++;                    memset(flag, 0, sizeof(flag));                    unAppearNum = K;                }            }        }        printf("%d\n", completeCollectionNum+1);    }}

一道考智力的题，不适合我这样的庸才，直接看后面的discusss:

证明子序列的长度至少为n，仅当序列是这样的()()...()[]，一个()是一次1..M出现的序列，共n个。必要性。数学归纳法。n>=1.序列显然是()[]，假设n>=如果n，k是，序列是k()+[]>=k+1.取第k()的最后一个元素。这个元素肯定会用在长度为k的子序列中。如果不能，就放在[]里。这样做第k()还是一次1。..M出现的序列，然后取前一个元素，由于n的归纳假设，第k()中必须有一个元素来满足要求>=k+所以这个元素之后必然会出现1..m的所有元素都是一次，所以[]=()[]‘充分性。太明显了，没有证书。

假设排序的数量为n，其最短的非子序长度可以通过以下方法获得。如果有一个最小的组合，包括全排序，(1，2，...n),(顺序不限，只要有1...n的数字就够了，也可能有重复的数字)找到所有这样的组合。可以合成()()()...()[],( 如果有k括号，[]中的元素可能是空的)，其最短的非子序长度为k+1;原因:长度为k的子序可以由前k个括号中的一个数组成。但是k+1找不到组合，因为最后一个组合需要的最后一个数量少了。 例如：14 515325134425123首先有(1、5、3、2、5、1、3、4)(4、2、5、1、2、3)[];

// | ... a1| | ... a2| ... | ac|| ... | // 后面的| ... | 是不完整的 1 - k // 完整的统计数据出现在前面 1 - k 的个数 c , c + 1 答案///// 设置每个完整的1 - k 以 ai结束( 1 <= i <= c )// 假设最后一个缺失 aj , 则无法构造 a1 a2 ... ac aj