•  
  • Archives for 动态规划 (36)

【HDU1003】Max Sum(最大子序列和)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 09 月 15 日

Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
题目说的不清楚,按照自己弄的一些数据测试出最终要的结果是:最长最大子序列和,如果有多个结果输出第一组。题目中没有体现出 “最长” 这一字眼。
(more...)

【HDU3348】coins(贪心,动态规划DP)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 12 日

"Yakexi, this is the best age!" Dong MW works hard and get high pay, he has many 1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10 Jiao) (more...)

【HDU1224】Free DIY Tour(动态规划DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 11 日

Weiwei is a software engineer of ShiningSoft. He has just excellently fulfilled a software project with his fellow workers. His boss is so satisfied with their job that he decide to provide them a free tour around the world. It's a good chance to relax themselves. To most of them, it's the first time to go abroad so they decide to make a collective tour.
(more...)

【HDU1223】Order Count(动态规划DP+java大数)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 11 日

If we connect 3 numbers with "< " and "=", there are 13 cases: 1) A=B=C 2) A=B(more...)

【POJ1692】Crossed Matchings(动态规划DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 10 日

There are two rows of positive integer numbers. We can draw one line segment between any two equal numbers, with values r, if one of them is located in the first row and the other one is located in the second row. We call this line segment an r-matching segment. The following figure shows a 3-matching and a 2-matching segment. (more...)

【POJ1717】Dominoes (动态规划,背包变形)

Categories: 数据结构和算法
Tags: ,
Comments: 1 Comment
Published on: 2011 年 05 月 09 日

A domino is a flat, thumbsized tile, the face of which is divided into two squares, each left blank or bearing from one to six dots. There is a row of dominoes laid out on a table: (more...)

【POJ2342】Anniversary party(树形动态规划 tree dp)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 06 日

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings. (more...)

【POJ2823】Sliding Window(单调队列的原理和简单应用)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 05 日

单调递减队列是这么一个队列,它的头元素一直是队列当中的最大值,而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素,可以从队列的两端删除元素。
(more...)

【POJ2411】Mondriaan's Dream(动态规划)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 04 日

discuss里看到的牛B方法。。。。短小精悍,看到后十分汗颜,就像做TC样。自己写老长的代码,跟排名前几的代码一比就像dog shit。要走的路还遥遥无期,根本没头啊~~~~。留下大家也观摩下吧。。。 (more...)

【POJ1260】Pearls (动态规划)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 03 日

题意:现在要买若干种价值的珍珠,但买某种珍珠必须多付10颗此种珍珠的价钱,一颗珍珠可以用比它贵的珍珠充数,因此有时候用贵的珍珠来代替便宜的可能更省钱,输入要买的若干种珍珠,在可用高价珍珠充数的条件下,问最少需要花费多少钱. (more...)

【POJ2479】Maximum sum(动态规划,DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 05 月 03 日

跟之前的求子段最大和差不多,不知道请看http://blog.pureisle.net/?p=266
这里求的是两个子段最大和,注意看数据,两个子段均不能为空(偶在这里多两次WA)。。。。另附POJ,discuss里边别人粘贴出来了一层循环写法。。。道理都差不多,时间也差不多。 (more...)

【POJ1179】Polygon (动态规划 DP)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 28 日

多边形游戏是一个单人玩的游戏,开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值,每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。

游戏第1步,将一条边删除。

随后n-1步按以下方式操作:

(1)选择一条边E以及由E连接着的2个顶点V1和V2;

(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。

最后,所有边都被删除,游戏结束。游戏的得分就是所剩顶点上的整数值。
(more...)

【POJ1125】Stockbroker Grapevine(动态规划,floyd)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 26 日

题意:股票Broker们需要在他们的客户中传播谣言,但是每个Broker只能传给他自己的顾客们。给出Broker们和他们所
拥有的顾客,求能让谣言传播从第一个人开始到最后一个客户的最短时间。使用Floyd算法。
输入样例是有多少经纪人,随后是每行第一个数是相应编号的经纪人联系的人,然后之后每对数表示联系的人的编号和联系需要花的时间。
(more...)

page 1 of 3»
文章归档
日历
2017年十一月
« 七    
 1234
567891011
12131415161718
19202122232425
2627282930  
标签云
sina weibo
我的广告可能就是你的信息

Welcome , today is 星期一, 2017 年 11 月 20 日