草庐IT

（蓝桥真题）分果果（动态规划）

AC__dream 2023-05-21 原文

题目链接：P8746 [蓝桥杯 2021 省 A] 分果果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

样例1输入： 

5 2
6 1 2 7 9

样例1输出：

0

样例2输入：

5 5
6 1 2 7 9

样例2输出：

2

分析：这道题的状态表示比较难想：首先我们先考虑一下有哪些东西需要维护：

1.当前分配到哪个小朋友

2.当前分配到的小朋友的糖果最小值

3.当前分配到的小朋友的糖果最大值

4.当前已经分配一次的糖果编号位置

5.当前已经分配两次的糖果编号位置

那么其中我们可以选择一个作为f数组的含义，其余的四个显然都需要枚举。我们可以考虑用f数组存储当前状态分配到的小朋友的糖果的最大值，那么我们就开始枚举剩余四个维度。

设f[i][j][k]表示第i个人取到的最后一个糖果编号是j，第i-1个人取到的最后一个糖果编号小于等于k时的最大重量的最小值

答案就是min(f[m][n][n]-mn)，所以我们要在mn一定的情况下尽可能减少f数组的值

首先要枚举的就是分配到的小朋友的糖果的最小值mn，那么我们每次考虑给小朋友分配一段连续的糖果区间就要注意区间和不能小于mn。

那么f[i][j][k]应该怎么更新呢？

首先有f[i][j][k]=f[i][j][k-1]，这个无需多言，由于f数组维护的最大值，那么从这个角度也可以看出随着k的增加f数组是非递增的

还有就是第i个人用了前i-1个人中已经分配两次糖果编号的后某个位置开始，不妨设为t

那么就有f[i][j][k]=max(f[i-1][k][t],s[j]-s[t]),s数组是前缀和

但是为了尽可能减少f数组的值，就要使得f[i-1][k][t]和s[j]-s[t]的值都尽可能小，我们可以发现，随着t的增大，这两个值都是在逐渐减小的，但是t也要有一个限制条件，就是因为我们给第i个人分配的糖果区间是[t,j]，所以这个区间内的糖果总数是要大于等于最小值mn的，所以这块我们可以。

有小伙伴可能会有疑问，为什么不能是从前i-1个人中已经分配一次糖果编号的后一个位置开始呢？这个是包含在上述情况的，因为分配两次糖果编号的位置一定是小于分配一次糖果编号的位置的，所以我们从分配两次糖果编号的位置开始分配总有一次会使得编号位置大于分配一次糖果编号的位置，这个时候原来的分配一次编号的位置就变为了分配两次编号的位置了，那么也就变成上述情况了。

还有就是从上面的分析，我们可以发现每次从分配两次的编号后面的某个位置t开始继续分配，此次分配后的位置都是大于等于分配一次的编号的位置，有没有可能是小于第一次分配编号的位置呢？这个是不可能的，因为如果小于第一次编号分配的位置，那么说明上次分配的区间是包含本次分配的区间的，那么我们完全可以把这两次分配调整为相交但不包含的情况，这样两个区间的最大值一定会减少，由于答案是最大值减去最小值，所以对答案也只会更优

其他就是一些细节上的问题了，可以看下代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=103;
int f[N][N][N],w[N],s[N];
/*
f[i][j][k]表示第i个人取到的最后一个糖果编号是j，第i-1
个人取到的最后一个糖果编号小于等于k时的最大重量的最小值 
*/
bool vis[N*N];//vis[i]记录存在一段区间满足区间和为i
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
		s[i]=s[i-1]+w[i];
		for(int j=0;j<i;j++)
			vis[s[i]-s[j]]=true;
	}
	int ans=0x3f3f3f3f;
	for(int mn=1;mn*m<=2*s[n];mn++)//枚举重量最小值 
	{
		if(!vis[mn]) continue;//剪枝 
		memset(f,0x3f,sizeof f);
		f[0][0][0]=0;
		for(int i=1;i<=m;i++)//枚举当前更新状态
		for(int k=0;k<=n;k++)//枚举第i-1个人选的最后一个糖果编号
		{
			int id=0;//找到第i-2个人选的最后一个糖果编号
			for(int j=k;j<=n;j++)//第i个人选的最后一个糖果编号 
			{ 
				if(k>0) f[i][j][k]=f[i][j][k-1];
				if(s[j]<mn) continue;//每个人选取的最小重量不能小于mn
				//第i个人选的区间是[id+1,j]
				while(id<k&&s[j]-s[id]>mn) id++;
				if(s[j]-s[id]<mn) id--;
				f[i][j][k]=min(f[i][j][k],max(f[i-1][k][id],s[j]-s[id]));
			}
		}
		ans=min(ans,f[m][n][n]-mn); 
	}
	printf("%d",ans);
	return 0;
}

蓝桥真题xff0cxffxff0动态规划算法蓝桥杯

有关（蓝桥真题）分果果（动态规划）的更多相关文章

  1. ruby - 在 Ruby 中动态创建数组 - 2

    有没有办法在Ruby中动态创建数组？例如，假设我想遍历用户输入的书籍数组:books=gets.chomp用户输入:"TheGreatGatsby,CrimeandPunishment,Dracula,Fahrenheit451,PrideandPrejudice,SenseandSensibility,Slaughterhouse-Five,TheAdventuresofHuckleberryFinn"我把它变成一个数组:books_array=books.split(",")现在，对于用户输入的每一本书，我想用Ruby创建一个数组。伪代码来做到这一点:x=0books_array.

  2. ruby - 是否可以将 IRB 提示配置为动态更改？ - 2

    我想在IRB中浏览文件系统并让提示更改以反射(reflect)当前工作目录，但我不知道如何在每个命令后进行提示更新。最终，我想在日常工作中更多地使用IRB，让bash溜走。我在我的.irbrc中试过这个:require'fileutils'includeFileUtilsIRB.conf[:PROMPT][:CUSTOM]={:PROMPT_N=>"\e[1m:\e[m",:PROMPT_I=>"\e[1m#{pwd}>\e[m",:PROMPT_S=>"FOO",:PROMPT_C=>"\e[1m#{pwd}>\e[m",:RETURN=>""}IRB.conf[:PROMPT_MO

  3. ruby-on-rails - carrierwave:在序列化动态属性上安装 uploader - 2

    首先，我使用的是rails3.1.3和来自master的carrierwavegithub仓库的分支。我使用after_init钩子(Hook)来确定基于属性的字段页面模型实例并为这些字段定义属性访问器将值存储在序列化哈希中(希望它清楚我是什么谈论)。这是我正在做的事情的精简版:classPage省略mount_uploader命令让我可以访问我想要的属性。但是当我安装uploader时出现错误消息说“nil类的未定义新方法”我在源代码中读到有方法read_uploader和扩展模块中的write_uploader。我如何必须覆盖这些来制作mount_uploader命令使用我的“虚拟

  4. ruby - 在 Ruby 中动态生成多维数组 - 2

    我正在尝试动态构建一个多维数组。我想要的基本上是这样的(为简单起见写出来):b=0test=[[]]test[b]这给了我错误:NoMethodError:undefinedmethod`test=[[],[],[]]而且它工作正常，但在我的实际使用中，我不会事先知道需要多少个数组。有一个更好的方法吗？谢谢 最佳答案 不需要像您正在使用的索引变量。只需将每个数组附加到您的test数组:irb>test=[]=>[]irb>test[["a","b","c"]]irb>test[["a","b","c"],["d","e","f"]]

  5. ruby-on-rails - 使用 gmaps4rails 动态加载谷歌地图标记 - 2

    如何只加载map边界内的标记gmaps4rails？当然，在平移和/或缩放后加载新的。与此直接相关的是，如何获取map的当前边界和缩放级别？ 最佳答案 我是这样做的，我只在用户完成平移或缩放后替换标记，如果您需要不同的行为，请使用不同的事件监听器:在你看来(index.html.erb):{"zoom"=>15,"auto_adjust"=>false,"detect_location"=>true,"center_on_user"=>true}},false,true)%>在View的底部添加:functiongmaps4rail

  6. ruby - 动态方法链？ - 2

    如何在对象上调用方法名称的嵌套哈希？例如，给定以下哈希:hash={:a=>{:b=>{:c=>:d}}}我想创建一个方法，给定上面的散列，执行以下操作:object.send(:a).send(:b).send(:c).send(:d)我的想法是我需要从一个未知的关联中获取一个特定的属性(这个方法不知道，但程序员知道)。我希望能够指定一个方法链来以嵌套哈希的形式检索该属性。例如:hash={:manufacturer=>{:addresses=>{:first=>:postal_code}}}car.execute_method_hash(hash)=>90210

  7. ruby - 如何使用 method_missing 动态声明方法？ - 2

    我有一个ruby​​程序，我想接受用户创建的方法，并使用该名称创建一个新方法。我试过这个:defmethod_missing(meth,*args,&block)name=meth.to_sclass我收到以下错误:`define_method':interningemptystring(ArgumentError)in'method_missing'有什么想法吗？谢谢。编辑:我以不同的方式让它工作，但我仍然很好奇如何以这种方式做到这一点。这是我的代码:defmethod_missing(meth,*args,&block)Adder.class_evaldodefine_method

  8. ruby - 动态扩展现有方法或覆盖 ruby​​ 中的发送方法 - 2

    假设我们有A、B、C类。Adefself.inherited(sub)#metaprogramminggoeshere#takeclassthathasjustinheritedclassA#andforfooclassesinjectprepare_foo()as#firstlineofmethodthenrunrestofthecodeenddefprepare_foo#=>prepare_foo()neededhere#somecodeendendBprepare_foo()neededhere#somecodeendend如您所见，我正在尝试将foo_prepare()调用注入

  9. ruby - 使用 jbuilder 创建具有动态哈希键的 JSON - 2

    这里我想输出带有动态组名的json而不是单词组@tickets.eachdo|group,v|json.group{json.array!vdo|ticket|json.partial!'tickets/ticket',ticket:ticketend}end@ticket是这样的散列{a:[....],b:[.....]}我想要这样的输出{a:[.....],b:[....]} 最佳答案 感谢@AntarrByrd，这个问题有类似的答案:JBuilderdynamickeysformodelattributes使用上面的逻辑我已经

  10. ruby - 在 Rakefile 中动态生成 Rake 测试任务(基于现有的测试文件) - 2

    我正在根据Rakefile中的现有测试文件动态生成测试任务。假设您有各种以模式命名的单元测试文件test_.rb.所以我正在做的是创建一个以“测试”命名空间内的文件名命名的任务。使用下面的代码，我可以用raketest:调用所有测试require'rake/testtask'task:default=>'test:all'namespace:testdodesc"Runalltests"Rake::TestTask.new(:all)do|t|t.test_files=FileList['test_*.rb']endFileList['test_*.rb'].eachdo|task|n

随机推荐