« 上一页下一页 »Current position : 首页 >> 动态规划 >> 第31页
「JoyOI1015」公路乘车
题目描述一个特别的单行街道在每公里处有一个汽车站。顾客根据他们乘坐汽车的公里使来付费。例如下表就是一个费用的单子。 没有一辆车子行驶超过10公里，一个顾客打算行驶n公里（1<=n<=100），它可以通过无限次的换车来完成旅程。最后要求费用最少。输入 第一行十个整数分别表示行走1到10公里的费用（<=500）。注意这些数并无实际的经济意义，即行驶10公里费用可能比行驶一公里少。 第二行一个整数n表示，旅客的...
「RQNOJ272」马棚问题
题目描述每天，小明和他的马外出，然后他们一边跑一边玩耍。当他们结束的时候，必须带所有的马返回马棚，小明有K个马棚。他把他的马排成一排然后跟随它走向马棚，因为他们非常疲劳，小明不想让他的马做过多的移动。因此他想了一个办法：将马按照顺序放在马棚中，后面的马放的马棚的序号不会大于前面的马放的马棚的序号。而且，他不想他的K个马棚中任何一个空置，也不想任何一匹马在外面。已知共有黑、白两种马，而且它们相处得并...
「JoyOI1048」田忌赛马
题目描述 中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了，他们各派出N匹马，每场比赛，输的一方将要给赢的一方200两黄金，如果是平局的话，双方都不必拿出钱。现在每匹马的速度值是固定而且已知的，而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马，才能赢取最多的钱？输入第一行为一个正整数n (n <= 1000) ，表示双方马的数量。第二行有N个整数表示田忌...
拦截导弹
题目描述 M-78星云上有丰富的矿产资源，而njn极想掠夺其资源，2月30日njn终于发动了对M-78星云的侵略战争。众多正义和平之士在jun的带领下来到M-78星云协助当地居民抵抗外来侵略。由于njn对M-78星云的战争迟迟不能结束，所以，njn终于使出杀手锏：发射导弹，攻击M-78星云。幸好jun事先已在njn的军营中安插间谍pzy。pzy不负众望，终于秘密的获得了njn要发射的n个导弹的高度。获的导弹机密后，jun又面临一个严峻的...
机器分配
题目描述描述Description 总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M<=15，N<=10。分配原则：每个公司有权获得任意数...
硬币找零
题目描述设有n种（n<=20）不同面值的硬币，各硬币的面值存于数组T[1..N]中，数据中至少有一枚硬币面值为1，现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数不限，请计算找出钱数m(1<=m<=10000)的最少硬币个数。输入：第一行为n种硬币和要找的钱数m;第二行为分别为n种硬币的面值t1,t2…tn输出：最小的硬币个数样例输入[crayon-676d65a80d832007980150/]样例输出[crayon-676d65a80d839347156661/]代码[crayon-...
导弹拦截问题系列
导弹问题1题目描述 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹?该导...
城市交通
题目描述有n个城市，编号1~n，有些城市之间有路相连，有些则没有，有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市，问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少？输入输入格式：先输入一个n，表示城市数，n<100。下面的n行，是一个n*n的邻接矩阵map[1..n,1..n]。map[i,j]=0，表示城市i和城市j之间没有路相连，否则为两者之间的距离。输出输出格式：一个数，表示从城市1走到城市n的最短距离...
最小中间和
题目描述给定一个正整数序列a1,a2,...,an，不改变序列中的每个元素在序列中的位置，把它们相加，并用括号记每次加法所得的和，称为中间和。编程：找到一种方法，添上n-1对括号，加法运算依括号顺序进行，得到n-2个中间和，使得求出使中间和最少。例如给出的序列是4，1，2，3。第一种添加括号方法：（（4＋1）＋（2＋3））＝（（5）＋（5））＝（10），有三个中间和是5,5，10，它们之和为5＋5＋10＝20；第二种添括号方法：（4＋（（...
数字三角形系列
数字三角形题目描述示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。 每一步可沿左斜线向下或右斜线向下走； 1<三角形行数<25； 三角形中的数字为整数<1000；输入第一行为N，表示有N行后面N行表示三角形每条路的路径权输出路径所经过的数字的总和最大的答案样例输入5738810274445265样例输出30提示 搜索80分，记忆化搜索AC 代码[crayon-676d65a80...
「RQNOJ166」免费午餐
题目描述为了增加顾客,Sally的店铺决定提供免费午餐,顿时门庭若市,但是不久Sally的原材料不足了….因此Sally决定公布一项决定:凡是来本店吃免费午餐的,一天吃能吃一次,吃的数量必须比上一次吃的少,点的必须在上一次后面，且免费午餐将只有N个种类任君选择,为了能吃到最多的免费午餐,你将如何安排每日吃的数量呢?输入格式第一行一个数N，表示免费午餐的种类（0<=N<=100000)第二行N个数，表示每个免费午餐的数量（0<...
「JoyOI1062」合并傻子
题目描述在一个园形操场的四周站着N个傻子,现要将傻子有次序地合并成一堆.规定每次只能选相邻的2个傻子合并成新的一个傻子，并将新的一个傻子的RP数，记为该次合并的RP数。（合并方法与NOI1999石子合并（本题库的沙子合并）相同，请大家参考上题合并方法）将N个傻子合并成1个的最小RP数为RPn和最大RP数为RPx.钟某人要合并他们，钟某人现在的RP为m,但是他要小心....if m>RPx then 钟某人能很轻松的合并他...
OI 课件=>
近期评论