POJ1989 The Cow Lineup 額，貪心？？

傳送門

題目大意：

給出n個數組成的一個串，這n個數的範圍是1~k，求出最短非子序列的串（這個串隻能由1~k中的數字組成）

分析：

額(⊙o⊙)…不會

題解是這麼寫的：

從前往後掃描，把原串劃分成若幹個序列，使得這些序列滿足包含所有的1~k的數字，并且至少有一個數字隻出現過一次，答案就是序列個數+1

代碼如下：

#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=+,maxk=+;
int n,k,a[maxn],ans;
bool vis[maxk];
inline int read(void){
    char ch=getchar();
    int f=,x=;
    while(!(ch>='0'&&ch<='9')){
        if(ch=='-')
            f=-;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        x=x*+ch-'0',ch=getchar();
    return f*x;
}
inline bool check(){
    for(int i=;i<=k;i++)
        if(!vis[i])
            return false;
    memset(vis,,sizeof(vis));
    return true;
}
signed main(void){
    n=read(),k=read(),ans=;
    for(int i=;i<=n;i++)
        a[i]=read();
    memset(vis,,sizeof(vis));
    for(int i=;i<=n;i++){
        vis[a[i]]=;
        if(check())
            ans++;
    }
    printf("%d\n",ans+);
    return ;
}
           

by >o< neighthorn