挑战程序设计竞赛
关注
分享
扫一扫
Strokess
懂的越少，想的越多。
展开
-
POJ 3617 Best Cow Line
题目链接：POJ 3617题意：给n个字符，如样例6个字符ACDBCB，从开头或者末尾选一个字符加到新字符串的末尾，使得到的新字符串字典序最小。注意输出每行最多80个字符。贪心，将原字符串与反转字符串比较来决定取哪里的字符串。挑战程序设计竞赛2.2.3 字典序最小问题#include #include #include #include using namesp原创 2016-07-24 12:40:51 · 459 阅读 · 0 评论 -
POJ 3069 Saruman's Army
题目链接：POJ 3069题意：第一行r 和 n，表示半径为r，n个点。要求每个点周围距离r以内（包括r和0）都必须有1个点被标记，问至少需要标记多少个点。思路：贪心，先从最左边点开始找与其距离最接近r且小于r的点，将此点标记，然后以此点开始向右找与其距离最接近r且大于r的点，将这个点作为新的起点，重复以上步骤。注意判断不能超过界限。挑战程序设计竞赛，贪心原创 2016-07-24 19:50:38 · 443 阅读 · 0 评论 -
动态规划 最长上升子序列（LIS）
O(N2)写法：memset(dp, 0, sizeof(dp))for(i = 0; i dp[i]= 1; for(j= 0; j if(s[j] }}O(nlogn)写法1：（ dp[i]存长度为i + 1的上升子序列中末尾元素的最小值）fill(dp, dp + n,原创 2016-07-27 16:44:48 · 4651 阅读 · 0 评论 -
POJ 2431 Expedition (贪心、优先队列）
题目链接：http://poj.org/problem?id=2431题意：起点到终点之间有n个加油站，输入第一行为n，后面n行每行是该加油站距终点的距离和能加多少油。1单位油能开1单位距离。最后一行是起点到终点的距离和初始油箱里有多少油。问最少加几次油能到终点，不能到的话输出-1 。先将所有的加油站按距离起点的距离从小到大排序，然后模拟车开的过程，每经过一个加油站只要油箱原创 2016-07-28 18:30:38 · 507 阅读 · 0 评论 -
开关问题 POJ 3276 POJ 3279 POJ 1222
POJ 3276题目链接：http://poj.org/problem?id=3276题意：N个牛 ，B表示朝后， F表示朝前，每次可以选择连续的K个牛反转方向，问如何选择K，使得操作数M最少，K也应尽量小。参考博客：http://www.cnblogs.com/neopenx/p/4071801.html①从第一头牛开始，如果朝前，不管了。看下一头牛，如果朝后反转K长度区原创 2016-08-15 12:16:43 · 897 阅读 · 0 评论 -
POJ 3255 Roadblocks （Dijkstra求次短路）
题目链接：http://poj.org/problem?id=3255题意：有E条路，V个节点，问1号到N号路口的次短路长度是多少？——挑战程序设计竞赛书上说到某个顶点v的次短路要么是到其他某个定点u的最短路再加上u->v的边，要么是到u的次短路再加上u->v的边。前半句比较好理解，因为最短路就是以这种形式更新的，后半句不是太懂......所以对代码也有些疑问，原创 2016-08-02 09:41:38 · 647 阅读 · 0 评论 -
POJ 3723 Conscription （求最大权森林，kruskal，并查集）
ConscriptionTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 9902 Accepted: 3502DescriptionWindy has a country, and he wants to build an army to protec原创 2016-02-13 17:40:05 · 938 阅读 · 0 评论 -
POJ 1064 Cable master （二分）
题目链接：http://poj.org/problem?id=1064题意：N条绳子，长度分别为Li。若从中切割出K条长度相同的绳子，这K条绳子每条最长能有多长。二分查找，下界为0上界为最大的L，答案不能四舍五入。用C++可以过，G++WA。。。为什么。。。#include #include #include #include #includ原创 2016-08-12 15:00:11 · 629 阅读 · 2 评论 -
POJ 2456 Aggressive cows （二分、贪心）
题目链接：http://poj.org/problem?id=2456题意：n个房子，m头牛，房子有一系列横坐标，问将m头牛塞进房子，每两头牛之间的最大间隔是多少。二分+贪心。#include #include #include #include #include #define eps 1e-6using namespace std;int n,原创 2016-08-12 15:44:23 · 507 阅读 · 0 评论