1428专题

HDU 1428 漫步校园 (搜索 + dp)

OJ题目:click here ~~ 题意分析:题目中有句话“他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。”,关键是对这句话的理解。此刻在A区域,选择下面要走的B区域的条件是,存在一条B区域到机房的路线比A区域到机房的所有路线都近,也就是说,存在一条B区域到机房的路线比A区域到机房的最短路线更近(比最短的近

lightoj 1428 Melody Comparison 后缀数组

题意:给定一个字符串A和字符串B,求A的不包含B的不同子串个数。 思路:首先把B串接到A串后面中间用一个A、B中均未出现的字符隔开,构成字符串s。求出每个字符对应的height[ i ]、sa[ i ]、rank[ i 。我们开一个rmax数组,rmax[ i ]存的是从A串的第i个字符向右能不形成包含B串的串的最长长度,那么我们必须先知道A串哪些位置 开始能形成B串。假设A串的长度为l

UVA 1428 - Ping pong(树状数组)

UVA 1428 - Ping pong 题目链接 题意:给定一些人,从左到右,每个人有一个技能值,现在要举办比赛,必须满足位置从左往右3个人,并且技能值从小到大或从大到小,问有几种举办形式 思路:利用树状数组处理出每个位置左边比它小的个数和右边比他小的个数和,那么左边和右边大就也能计算出来,那么比赛场次为左边小*右边大+左边大*右边小。 代码: #include <cs

hdu_1428 漫步校园

原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1428 分析:(属于简单的综合题,最短路(图论)+记忆化搜索(DP))              由“他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)” 知道,先要求出每个点到终点的最短路径。   接着DFS得到可以满足条件的路径个数

51Nod_1428 活动安排问题【贪心】

51Nod_1428 活动安排问题                                   http://www.51nod.com/Challenge/Problem.html#!#problemId=1428     题目 有若干个活动,第i个开始时间和结束时间是[Si,fi),同一个教室安排的活