本文出自 http://blog.csdn.net/shuangde800
---------------------------------------------------------------------------------
题意
刘汝佳请了K个客人到他家吃晚饭,加上他的家人:他的老婆、儿子、女儿、妈妈、爸爸、岳父、岳母,
那么这顿晚饭一共有K+8个人。因为是吃中餐,所以需要筷子,他家里一共有N根筷子,而且长短不一,
这时刘汝佳的ACMer本性又暴露出来了,他不按照正常的每个人都给两只筷子,而是每个人分3根筷子,
其中最长的一根用来叉比较大块的食物,而另外两根较短的筷子当作正常的使用。为了让每个人用得
更加舒服,显然,要让短的两根筷子长度尽量接近,设这三根筷子的长度为A,B,C(A<=B<=C),那么较小
两根会有一个平方差(A-B)^ 2。刘老师要你帮他算,怎样分配,所有人的平方差之和最小?
思路
long long ago,这题已经放着很多天了吧,可能有两个星期了。
期间本来想和nothi讨论一下,结果他说在高中时做过,好吧,搞过noip的人题目就是做得多。。。
然后去翻了下那道noi题(njupt 1581),看了下发现原题很简单。
原题是每个人只要两根筷子,要让所有人的筷子长度平方差之和最小。那么显然从小到大排序一下,
f(i, j)表示前i跟筷子,分配给j个人的最方差之和。因为所以加道理,可以知道一定要选择相邻的两个
筷子才能让平方差尽量少,所以得到状态转移
f(i, j) = min{ f(i-1, j), f(i-2, j-1) + (len[i]-len[i-1])^2 }
可能正是因为先AC了原题,所以一直限制了我的思路,一直按照上面类似的思路,从小到大排序,然后状态转移,
但是因为多了第三根最长的,所以不好想。
如果从小到大排序的话,状态表示会有一个问题, f(i, j)的第i根,一定是最大的那个,所以他一定不会取,这样
就给状态转移带来了困难。
后来的某一天,终于想到了:要是从大到小排序会怎样呢?那么f(i, j)的第i根,一定是最小的那根,所以他就可以
取了!
然后还有一个问题,要确定以i, i-1作为一双筷子时,前面还有一根筷子可以作为三根最长的那一根,那么,
只要保证(i-2)-(j-1)*3 >= 1,即前面j-1个人分配完以后至少还剩下有1根筷子,就一定可以作为当前i, i-1组
的最长那根!
状态转移就这样出来了:
当(i-2)-(j-1)*3 < 1时
f(i, j) = f(i-1, j);
当(i-2)-(j-1)*3 >= 1时
f(i, j) = min{f(i-1, j), f(i-2, j-2) + (len[i]-len[i-1])^2}
Perfect!
代码
<script src="https://code.csdn.net/snippets/858.js" type="text/javascript"></script>
分享到:
相关推荐
杭州ACM-Chopsticks解题
英语作业4-Fan chopsticks.doc
Chopsticks是一个orchestration 库,可以通过SSH远程管理和配置主机。Chopsticks对标的项目是fabric和ansible,不同的是,它不是把命令最终发给bash,而是让你在一个类似Python终端的环境中操作。它也支持Docker。
筷子手游戏JS 关于 从未听说过筷子游戏吗? 这是一个简单的基于回合的手形游戏,其中两个玩家从手到手转移点(如伸出的手指数所示)。 游戏规则 游戏以每手一分开始,当玩家输掉所有分后结束游戏。...
Chopsticks1
chopsticks是用于日常使用的Scala库的重要集合。 它是专门为构建高性能,生产级功能性React流系统而设计的。 这些已在我们的内部生产流系统中得到广泛使用,多年来,处理持久性写入次数超过一百万次/秒,而每台...
筷子(游戏)探索 具有作为依赖项。 此应用程序计算表示筷子游戏可能状态之间的联系的图形。 每个状态都通过几种可能的动作与其他状态相关联,这些动作包括: 以轮到该玩家的一只手的手指数,并将其添加到另一...
外研一起小学英语五下《Module9Unit 2 Mum bought new chopsticks for you.》word教案.docx
寿司卷 :sushi: 字节大小的与寿司金融互动的方式 :chopsticks:
餐饮_哲学家_问题在计算机科学中,进餐哲学家问题是并发算法设计中经常使用的一个示例问题,用于说明同步问题和解决这些问题的技术。 它最初是由Edsger Dijkstra于1965年制定的,它是一项学生考试练习,以计算机竞争...
筷子 1,基于Java8的快速入门Web框架 2,使用Netty,不依赖JavaEE,所以不能使用servlet,jsp,部署也不需要tomcat 3,ioc,mvc参考弹簧的实现 4,内置JSON输出
1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断出来 1026 Modular multiplication of polynomials 简单题,有比较简单的好算法 1307 Packets 简单题,不过也蛮经典的…… 1312 ...
1028 Flip and Shift 简单题,可以DP/BFS/……,但是实际上有数学方法可直接判断出来 1026 Modular multiplication of polynomials 简单题,有比较简单的好算法 1307 Packets 简单题,不过也蛮经典的…… 1312 ...
chopsticks the missing android layouter. It is sometimes a pain to layout your views programmatically using Java codes. The Java API cannot be used as the same way as XML. Chopsticks is the rescue. ...
:chopsticks: 通过Apigateway创建端点。 从serverless.yml创建资源。 连接到现有资源dynamodb 。 简要介绍graphql端点和lambda。 我们建造了什么 免责声明 :bowl_with_spoon: 使用它需要您自担风险,我创建了...
Chopsticks 类:设置筷子的各种参数和使用方法,例如是否被使用,设置筷子的状态 Philosopher 类:设置哲学家的思考、等待和吃饭方法。 详细介绍参考:...
Rax是用于构建通用应用程序的渐...快速开始 :chopsticks: :cooked_rice: 从命令行开始 使用create-rax创建一个新的Rax项目: $ npm init rax npm init 在npm 6+中可用 启动本地服务器以启动项目: $ cd < YourP
快速入门 :chopsticks: :cooked_rice: 从命令行开始使用 create-rax 创建一个新的 Rax 项目: $ npm init rax 初始化 在 npm 6+ 中可用启动本地服务器来启动项目:$ cd $ npm install $ npm run start 从 VS Code ...