来自CY的礼物


T1:导弹拦截

题意:就是求最长不升子序列和最长下降子序列长度,要求是O(nlogn)的算法

看到这题一股气每喘上来,前几天刚看的最长某某序列nlogn优化,结果觉得太偏门了,没有学,结果。。。考场上临时脑补出来了。其实我只打了最长下降子序列的算法,对于最长上升子序列,只要对数组每个元素求个相反数即可(把导弹改成潜艇)。

虽然代码很丑,但是还是可以AC的


T2:整数划分

题意:把一个整数划分为m个部分,使这几个部分的乘积最大。

如果mul[i][j]表示原数[i...j]部分的值,mx[i][j]表示原数[1...i]部分划分j次的最大乘积,那么mx[j][i]=mx[k][i-1]×mul[k+1][j];

一个错误代码:如果遇到有0但是要将原数分解为几个一位数乘积的情况会错

更改后的正确代码(在错误代码的44行后添加了一段)


T3:快餐问题

题意:Peter最近在R市开了一家快餐店,为了招揽顾客,该快餐店准备推出一种套餐,该套餐由A个汉堡,B个薯条和C个饮料组成。价格便宜。为了提高产量,Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡、薯条和饮料,由于每条生产线每天所能提供的生产时间是有限的、不同的,而汉堡、薯条和饮料的单位生产时间又不同,这使得Peter很为难,不知道如何安排生产才能使一天中生产的套餐产量最大。请你编写程序,计算一天中套餐的最大生产量。为简单起见,假设汉堡、薯条和饮料的日产量不超过100个。

这道题我考场上进行骗分,骗到60分。事后想想,当初要不是没看完题,其实我可以骗100分的

正解:

100分骗分(无论是考试还是CodeVS)


T4:物品装箱

题意:有n个物品及其替代品,(n<=100),装到容积为TOT(TOT<=10000)的包内,第i个物品和其替代品中至多有1个装入箱子。每个物品及其替代品都有一个大小和价值,求箱子内物品的最大价值和

水水水,分组背包也不出难点