P2072 宗教问题
GUO120822
·
·
题解
这是一道妥妥的动态规划。
出题人也是真牛，出了一道二合一的题。
好了，步入正题。
思路
我们先来看第一小问：这 N 个教徒至少要分为几个集体。
我们很容易想到用 f_i 表示前 i 个人，至少要分成多少组。
对于每个 f_i，枚举它的断点，然后加上 j 到 i 的贡献。
再来看第二小问：这些集体的危险值总和至少为多少。
- 状态设计
同样的，我们用 $dp_i$ 表示前 $i$ 个人，种类数和的最小值。
- 动态转移方程
也是枚举断点。
$dp_i=\min(dp_i,dp_{j-1}+sum_{j,i})$。
$sum_{j,i}$ 表示从 $j$ 到 $i$ 的种类数。
直接枚举会超时，我们就倒序枚举，每次加上种类数，在枚举时统计。
再二合一，得到[代码](https://www.luogu.com.cn/record/143440552)。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1010,M=30,inf=0x3f3f3f3f;
int n,m,k,i,j,f[N],dp[N],cnt[M],a[N],sum;
int main()
{
scanf("%d%d%d",&n,&m,&k);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
for (i=1;i<=n;i++)
{
f[i]=dp[i]=inf;
memset(cnt,0,sizeof(cnt));
sum=0;
for (j=i;j>=1;j--)
{
if (!cnt[a[j]])
{
cnt[a[j]]++;
sum++;
}
if (sum>k) break;
f[i]=min(f[i],f[j-1]+1);
dp[i]=min(dp[i],dp[j-1]+sum);
}
}
printf("%d\n%d",f[n],dp[n]);
return 0;
}
```