自动搬运

查看原文

来自洛谷，原作者为

	06ray 再见了，OI

搬运于2025-08-24 21:33:40，当前版本为作者最后更新于2018-05-06 16:45:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题是道非常水的dp题。

思路如下：

1. 先读入题目中要求读入的n,m,k和每个教徒信的宗教编号。

2. 开始写核心部分。

   ①定义两个数组为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);
   

   自己可以慢慢体会含义，看完上面的解释应该能懂（不写原因其实是作者语文水平太差）

3. 最后我们就可以输出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 如果此题解有地方说的不好或是说错了，请在评论区告诉作者错误原因，谢谢！