题解 P2072 【宗教问题】
这题是道非常水的dp题。
思路如下：
-
先读入题目中要求读入的n,m,k和每个教徒信的宗教编号。
-
开始写核心部分。
①定义两个数组为f和dp，f[i]表示前i个教徒至少要分为几个集体，dp[i]表示前i个集体的危险值总和至少为多少。
②确定边界，这个比较好写，f[1]=a[1]（注：a[1]是第1个教徒信的宗教编号）;dp[1]=1。
③确定循环。共两层循环。第一层循环是从1到n，遍历n个教徒，用i作循环变量；第二层循环是从i到1逆序循环，循环变量j枚举的是前i个教徒的最后一个集体中的第一个教徒序号（也可以说是确定最后集体的大小）。
④判断前i个教徒的最后一个集体是否满足题目中条件。这并不难，首先定义一个桶，再定义统计最后集体里不同宗教编号数量为n1。发现如果第j个教徒所信仰的宗教编号没有出现过，那么就标记第j个教徒所信仰的宗教编号出现过，并且n1++。当发现n1大于k时，就直接break（想想为什么可以这样做）。
⑤现在就开始推状态转移方程了。其实方程特别好写，如下
f[i]=min(f[i],f[j-1]+1); dp[i]=min(dp[i],dp[j-1]+n1);自己可以慢慢体会含义，看完上面的解释应该能懂（
不写原因其实是作者语文水平太差） -
最后我们就可以输出f[n]和dp[n]了。
时间复杂度为O(n^2)
上代码 ( ^_^ )
注意：减少代码复制，共创美好洛谷！
#include <iostream>
#include <cstring>//头文件
using namespace std;//名字空间
int f[10000],dp[10000];//f数组存的是前i个教徒至少要分为几个集体的解，dp数组存的是前i个集体最小的危险值总和
int a[10000];//a数组存的是每个教徒信的宗教编号
bool b[10000];//这是一个桶
int main()
{
int n,m,k;
cin>>n>>m>>k;//读入
for(int i=1; i<=n; i++)
cin>>a[i];//读入
f[1]=1;
dp[1]=1;//定义边界
for(int i=2; i<=n; i++)
{
f[i]=10000000;
dp[i]=10000000;//dp[i]和f[i]一开始要赋一个较大的数
memset(b,0,sizeof(b));//初始化，很重要
int n1=0;//n1统计最后集体里不同宗教编号数量
for(int j=i; j>=1; j--)//逆序枚举
{
if(!b[a[j]])//如果第j个教徒所信仰的宗教编号没有出现过
{
n1++;//总数加1
b[a[j]]=true;//标记第j个教徒所信仰的宗教编号出现过
}
if(n1>k) break;//跳出当前循环
f[i]=min(f[i],f[j-1]+1);
dp[i]=min(dp[i],dp[j-1]+n1);//直接套用状态转移方程
}
}
cout<<f[n]<<endl<<dp[n];//输出解
return 0;//养成良好的编程习惯
}p.s 如果此题解有地方说的不好或是说错了，请在评论区告诉作者错误原因，谢谢！