欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ3377
题意概括
给出一个序列，序列中的数字为1~k中的。
让你求最短的非子序列长度。
题解
我们把构建非子序列看作在原序列中行走。
我们考虑当前走到了第i个数字，然后我们要选择后面的数字使得答案最短。
那么我们必然要尽量选择一步能到达的最远的方案（当然最好是直接走到终点）。
如果，在i后面的序列中，你要走到某一个位置，这个位置的值为v，那么在i+1到这个位置之间，就不可以存在任何位置使得该位置上的值与v相等，不然的话，我们是可以直接走到后面的那个v。但是实际上，走到前面的那个v，会生成更多的子序列，那么直接走到后面的那个就是不严谨的了。
所以，我们要从i+1开始走的尽量远，就是走到1~k中的最后一种数字出现时，选择一步走到这个位置，然后长度+1。
具体操作很简单啊，不多说了。
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=100005,K=10005;
int n,k,a[N],bh[K];
int main(){
scanf("%d%d",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
int L=0,R=0,ans=1,tot;
while (R<n){
memset(bh,0,sizeof bh);
tot=k;
while (R<n&&tot>0){
R++;
if (!bh[a[R]])
bh[a[R]]=1,tot--;
}
if (tot==0){
ans++;
L=R;
}
}
printf("%d",ans);
return 0;
}