第一篇：wikio(天梯：贪心,区间型动归,最短路径,最小生成树)总结
1214 线段覆盖
题目描述 Description
给定x轴上的N（0 输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。输出描述 Output Description 输出第一行是一个整数表示最多剩下的线段数。样例输入 Sample Input 3 6 3 1 3 2 5 样例输出 Sample Output 2 数据范围及提示 Data Size & Hint 0 1098 均分纸牌 题目描述 Description 有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。 移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。 现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。 例如 N=4，4 堆纸牌数分别为： ① 9 ② 8 ③ 17 ④ 6 移动3次可达到目的： 从 ③ 取 4 张牌放到 ④（9 8 13 10）-> 从 ③ 取 3 张牌放到 ②（9 11 10 10）-> 从 ② 取 1 张牌放到①（10 10 10 10）。输入描述 Input Description 第一行N（N 堆纸牌，1 <= N <= 100）第二行A1 A2 … An（N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）输出描述 Output Description 输出至屏幕。格式为： 所有堆均达到相等时的最少移动次数。‘ 样例输入 Sample Input 4 9 8 17 6 样例输出 Sample Output 3 数据范围及提示 Data Size & Hint e 1048 石子归并 题目描述 Description 有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。 输入描述 Input Description 第一行一个整数n（n<=100） 第二行n个整数w1,w2...wn(wi <= 100)输出描述 Output Description 一个整数表示最小合并代价 样例输入 Sample Input 4 4 1 1 4 样例输出 Sample Output 18 1154 能量项链 题目描述 Description 在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为m*r*n（Mars单位），新产生的珠子的头标记为m，尾标记为n。 需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为： (4⊕1)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。输入描述 Input Description 第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i 输出描述 Output Description 只有一行，是一个正整数E（E≤2.1*109），为一个最优聚合顺序所释放的总能量。样例输入 Sample Input 4 2 3 5 10 样例输出 Sample Output 710 1166 矩阵取数游戏 题目描述 Description 【问题描述】 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m 的矩阵，矩阵中的每个元素aij均 为非负整数。游戏规则如下： 1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素； 2.每次取走的各个元素只能是该元素所在行的行首或行尾； 3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分= 被取走的元素值*2i，其中i 表示第i 次取数（从1 开始编号）； 4.游戏结束总得分为m次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 输入描述 Input Description 第1行为两个用空格隔开的整数n和m。第2~n+1 行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。输出描述 Output Description 输出 仅包含1 行，为一个整数，即输入矩阵取数后的最大得分。样例输入 Sample Input 2 3 1 2 3 3 4 2 样例输出 Sample Output 82 数据范围及提示 Data Size & Hint 样例解释 第 1 次：第1 行取行首元素，第2 行取行尾元素，本次得分为1*21+2*21=6 第2 次：两行均取行首元素，本次得分为2*22+3*22=20 第3 次：得分为3*23+4*23=56。总得分为6+20+56=82 【限制】 60%的数据满足：1<=n, m<=30, 答案不超过1016 100%的数据满足：1<=n, m<=80, 0<=aij<=1000 最小生成树 1231 最优布线问题 题目描述 Description 学校需要将n台计算机连接起来，不同的2台计算机之间的连接费用可能是不同的。为了节省费用，我们考虑采用间接数据传输结束，就是一台计算机可以间接地通过其他计算机实现和另外一台计算机连接。 为了使得任意两台计算机之间都是连通的（不管是直接还是间接的），需要在若干台计算机之间用网线直接连接，现在想使得总的连接费用最省，让你编程计算这个最小的费用。输入描述 Input Description 输入第一行为两个整数n,m（2<=n<=100000，2<=m<=100000），表示计算机总数，和可以互相建立连接的连接个数。接下来m行，每行三个整数a,b,c 表示在机器a和机器b之间建立连接的话费是c。(题目保证一定存在可行的连通方案, 数据中可能存在权值不一样的重边，但是保证没有自环)输出描述 Output Description 输出只有一行一个整数，表示最省的总连接费用。样例输入 Sample Input 3 3 1 2 1 1 3 2 2 3 1 样例输出 Sample Output 2 数据范围及提示 Data Size & Hint 最终答案需要用long long类型来保存 1078 最小生成树 题目描述 Description 农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了使花费最少，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过100000 输入描述 Input Description 第一行： 农场的个数，N（3<=N<=100）。 第二行..结尾: 接下来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们每行限制在80个字符以内，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为线路从第i个农场到它本身的距离在本题中没有意义。输出描述 Output Description 只有一个输出，是连接到每个农场的光纤的最小长度和。样例输入 Sample Input 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 样例输出 Sample Output 28 最短路 1041 Car的旅行路线 题目描述 Description 又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。 那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。任务 找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。 输入描述 Input Description 第一行为一个正整数n(0<=n<=10)，表示有n组测试数据。每组的第一行有四个正整数s，t，A，B。 S(0 输出描述 Output Description 共有n行，每行一个数据对应测试数据。样例输入 Sample Input 1 3 10 1 3 1 1 1 3 3 1 30 2 5 7 4 5 2 1 8 6 8 8 11 6 3 样例输出 Sample Output 47.5 1077 多源最短路 题目描述 Description 已知n个点(n<=100)，给你n*n的方阵，a[i,j]表示从第i个点到第j个点的直接距离。 现在有Q个询问，每个询问两个正整数，a和b，让你求a到b之间的最短路程。满足a[i,j]=a[j,i];输入描述 Input Description 第一行一个正整数n，接下来n行每行n个正整数，满足a[i,i]=0,再一行一个Q，接下来Q行，每行两个正整数a和b。输出描述 Output Description 一共Q行，每行一个整数。样例输入 Sample Input 3 0 1 1 1 0 3 1 3 0 1 2 3 样例输出 Sample Output 2 数据范围及提示 Data Size & Hint n<=100，Q可能非常大。g[i][j]均>=0 请使用flyod算法 1079 回家 题目描述 Description 现在是晚餐时间,而母牛们在外面分散的牧场中。农民约翰按响了电铃,所以她们开始向谷仓走去。你的工作是要指出哪只母牛会最先到达谷仓(在给出的测试数据中,总会有且只有一只最快的母牛)。在挤奶的时候(晚餐前),每只母牛都在她自己的牧场上,一些牧场上可能没有母牛。每个牧场由一条条道路和一个或多个牧场连接(可能包括自己)。有时，两个牧场(可能是字母相同的)之间会有超过一条道路相连。至少有一个牧场和谷仓之间有道路连接。因此,所有的母牛最后都能到达谷仓,并且母牛总是走最短的路径。当然,母牛能向着任意一方向前进,并且她们以相同的速度前进。牧场被标记为'a'..'z'和'A'..'Y',在用大写字母表示的牧场中有一只母牛,小写字母中则没有。谷仓的标记是'Z',注意没有母牛在谷仓中。注意'm'和'M'不是同一个牧场否则错误上面的意思是说：输入数据中可能会同时存在M,m（郁闷ing)，比如 M a a m m z 输入描述 Input Description 第 1 行: 整数 P(1<= P<=10000),表示连接牧场(谷仓)的道路的数目。 第 2..P+1行: 用空格分开的两个字母和一个整数: 被道路连接牧场的标记和道路的长度(1<=长度<=1000)。输出描述 Output Description 单独的一行包含二个项目:最先到达谷仓的母牛所在的牧场的标记,和这只母牛走过的路径的长度。样例输入 Sample Input 5 A d 6 B d 3 C e 9 d Z 8 e Z 3 样例输出 Sample Output B 11
点击咨询 