P2072 宗教问题

很奇怪的dp，我是没有见过这种的之前，尤其是第二维倒着推，实际上就是把每种可能的分块情况枚举一遍,最后再输出答案,秒题

#include <bits/stdc++.h>
using namespace std;
int bk[1005],a[1005],p=0,f1[1005],f2[1005];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    f1[1]=f2[1]=1;
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int i=2;i<=n;i++)
    {
        f1[i]=1<<30;
        f2[i]=1<<30;
        memset(bk,0,sizeof(bk));
        int sum=0;
        for(int j=i;j;j--)
        {
            if(!bk[a[j]])
            {
                sum++;
                bk[a[j]]=1;
            }
            if(sum>k)
            break;
            f1[i]=min(f1[i],f1[j-1]+1);
            f2[i]=min(f2[i],f2[j-1]+sum);
        }
    }
    printf("%d\n%d",f1[n],f2[n]);
}