•  
  • Archives for POJ (26)

【POJ1961】Period(KMP算法,next函数)

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

For each prefix of a given string S with N characters (each character has an ASCII code between 97 and 126, inclusive), we want to know whether the prefix is a periodic string. (more...)

【POJ2406】Power Strings(KMP算法)

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

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n). (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...)

【POJ1160】Post Office(动态规划 DP)

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

题目给出一条直线上的m个村庄及其距离,给出n个邮局,要求怎么建n个邮局使代价最小。

思路:用opt[i][j]记录把前i个邮局建到前j个村庄中的最优解,用cost[i][j]记录所有在i到j村庄中,建1个邮局的最小代价。显然邮局应该设到中点。让前i个邮局覆盖前j个村庄,第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n),则状态转移方程为
res[i+1][j+k]=min{res[i][j]+cost[j+1][j+k];} (k+j<=n)

Cost数组存放从i到j中有一个邮局的最小代价,显然该邮局应该放在中间,构造cost的代码参考后边贴的代码。
(more...)

【POJ1014】Dividing (动态规划,多重背包)

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

思想:本题是找按价值均分大理石的方案是否存在,由于分配时不能破坏大理石,所以有个显而易见的剪枝:当所有的大理石的总价值为奇数时肯定不能被均分。把问题转化一下即:由一个人能否从原大理石堆中取出总价值为原来一半的大理石,本题的主要算法是动态规划,数组flag代表状态,设总价值为sum.当flag[k]==true时,说明,可以有一人获得价值k,另外一人获得价值V-k的大理石分配方案。反之若flag[k]=false说明这种分配方案不存在.我们的任务就是计算出flag[sum/2]是true还是false,显然有flag[0]==true的方案存在,即一个人什么都不分,另外一个人拿走全部的大理石. (more...)

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

Welcome , today is 星期日, 2017 年 11 月 19 日