洛谷 P2072 *问题

题目传送门

f[i]表示到第i个信徒的最少集体数,ans[i]为最小危险值.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>

using namespace std;

int n,m,k,p[1001],f[1001],ss,a[1001],ans[1001];
set<int> o;

inline int sum(int l,int r) {
    o.clear();
    for(int i = l;i <= r; i++)
        o.insert(a[i]);
    return o.size();
}

int main() {
    memset(f,0x3f3f3f,sizeof(f));
    memset(ans,0x3f3f3f,sizeof(ans));
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1;i <= n; i++)
        scanf("%d",&a[i]);
    for(int i = 1;i <= n; i++) {
        o.clear();
        for(int j = i;j >= 1; j--) {
            o.insert(a[j]);
            if(o.size() > k) {//找到可以划分到的最右端点 
                p[i] = j + 1;
                break;
            }
        }
        if(p[i] == 0) p[i] = 1;
    }
    f[0] = 0;
    f[1] = 1;
    ans[1] = 1;
    ans[0] = 0;
    for(int i = 2;i <= n; i++)
        for(int j = p[i] - 1;j < i; j++) {
            ss = sum(j + 1,i);
            f[i] = min(f[i],f[j] + ss);
            ans[i] = min(ans[i],ans[j] + 1);
        }
    printf("%d
%d",ans[n],f[n]);
    return 0;
}