题目背景
在一个地区有许多种宗教,不同信仰的教徒经常发生矛盾,最为治安管理的人需要把这些人分开,以免矛盾激化。
题目描述
已知一个地方有M种宗教(编号为1—M),有N个教徒(编号为1—N),每个教徒信且只信一种宗教。现在要按顺序把这N个教徒分成一些集体,每个集体的危险值定义为这个集体中的宗教种数,且一个集体的宗教种类不能超过K种,否则就会无限危险,
问: 1.这N个教徒至少要分为几个集体,
2.这些集体的危险值总和至少为多少。
输入格式
第一行三个正整数N M K,以空格隔开
第二行N个正整数,为每个教徒信的宗教编号
输出格式
第一行 一个正整数,为最少集体数
第二行 一个正整数,为最小危险值。
输入输出样例
输入 #1
10 4 3 1 2 3 4 3 4 3 2 1 2
输出 #1
3 6
说明/提示
【样例解释】
最少集体数:1 2 3 // 4 3 4 3 2 // 1 2 共3个集体
最小危险值:1 2 // 3 4 3 4 3 // 2 1 2 2+2+2=6
【数据范围】
对于20%的数据 N≤20
对于50%的数据 N≤100
对于100%的数据 N≤1000 M≤20 1≤K<M
题解:线性dp*2
#include<cstdio> #include<iostream> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<map> typedef long long ll; using namespace std; const int N=1005; const int oo=0x3f3f3f3f; int n,m,k,a[N],f[N],dp[N],vis[N]; int main(){ freopen("2072.in","r",stdin); freopen("2072.out","w",stdout); scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); f[1]=1; dp[1]=1; for(int i=2; i<=n; i++){ dp[i]=f[i]=oo; memset(vis,0,sizeof(vis)); int cnt=0; for(int j=i;j>=1;j--){ if(!vis[a[j]]) { cnt++; vis[a[j]]=true; } if(cnt>k) break; f[i] =min(f[i],f[j-1]+1); dp[i]=min(dp[i],dp[j-1]+cnt); } } printf("%d\n%d",f[n],dp[n]); return 0; }