1 Chao__King

尚未进行身份认证

暂无相关简介

等级
TA的排名 38w+

poj1664放苹果之动态规划

题意:把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?分析:建立状态转移方程:1、dp[i][1]=1; (m个苹果放到1个盘子)2、dp[1][j]=1,dp[0][j]=1; (一个苹果放到n个盘子以及每个盘子放一个苹果)3、dp[i][j]=dp[i][j-1]+dp[i-j][j];(i>=j,i个苹果放到j-1个盘子中,至少存在一...

2019-09-04 00:44:39

浅谈二分(poj3122分蛋糕)

题意:作者要开一个生日聚会,他现在拥有n块高度都为1的圆柱形奶酪,已知每块奶酪的底面半径为r不等,作者邀请了f个朋友参加了他的聚会,他要把这些奶酪平均分给所有的朋友和他自己(f+1人),每个人分得奶酪的体积必须相等(这个值是确定的),形状就没有要求。现在要你求出所有人都能够得到的奶酪的体积的最大值可以是多少?思路:类似二分查找。设置上界high为每个人分得奶酪的体积的所有可能值的最大值,初值...

2019-09-03 19:40:38

浅谈递归回溯法

概述:回溯法思路的简单描述是:把问题的解空间转化成了图或树的结构表示,然后使用深度优先搜索(dfs)策略进行遍历,遍历的过程中记录和寻找所有可行解或最优解。回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树,当算法搜索至解空间树的某一节点时,先利用剪枝函数判断该节点是否可行(即能得到问题的解)。如果不可行,则跳过对该节点为根的子树的搜索,逐层向其祖先节点回溯;否则。进入该...

2019-09-03 13:09:44

poj1856题解(深搜)

题意:欧美人喜欢玩一种叫做“海战棋”的棋类游戏。在这个游戏中,棋盘是一个矩形网格,每个网格可以摆放战船模型,战船模型可以看作一个矩形,占据了若干个网格。这些战船模型都是大小不一的,如果若干相邻的多个战船模型能一起构成一个更大的矩形,则认为这些战船能和平共处,不会相撞,但若一艘船与一艘有边相邻却无法构成矩形,或者这两艘战船有角相邻,那么认为这两艘船相撞。如在下图中,上方黑色和绿色的战船一起构...

2019-08-31 11:47:52

浅谈尺取法

尺取法:顾名思义,像尺子一样取一段,借用挑战书上面的话说,尺取法通常是对数组保存一对下标,即所选取的区间的左右端点,然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多,尤其是数据量大的时候,所以说尺取法是一种高效的枚举区间的方法,是一种技巧,一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方,有些情况下尺取法不可行,无法得出正确答案,...

2019-08-27 22:17:40

最长公共序列与子串

最长公共子序列:给你两个字符串s1=”abcfbc”, S2=”abfcab”,按下标递增求最长子序列的公共长度(可以不连续)len1=strlen(s1),len2=strlen(s2)状态转移方程:dp[i][0]=0 (0<=i<=len1)dp[0][j]=0 (0<=j<=len2)dp[i][j]=dp[i-1][j-1]+1 (s1[i]=...

2019-08-27 00:04:27

poj3268最短路径

描述N个农场(1≤N≤1000)各1头奶牛,方便编号1。N将参加在农场#X(1≤X≤N)举行的大型奶牛聚会,共计M(1≤M≤100,000)个单向(单行道连接成对农场;i路要求Ti(1≤Ti≤100)时间单位穿越。每头牛都必须步行去参加聚会,聚会结束后,再回到她的农场。每头牛都很懒,因此会选择最短时间内的最佳路线。牛的回程路线可能与它原来去派对的路线不同,因为路是单向的。在所有的牛中,一头牛走着去...

2019-08-17 16:34:10

学生信息管理系统

#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<fstream>#include<algorithm>using namespace std;const in...

2019-08-17 13:21:56

浅谈ST表应用

我们都知道,如果要查询一个区间的最值,那么最简单的办法就是用for循环,它的时间复杂度为O(n),如果要查询m次呢?那么它的时间复杂度就是O(n*m),显然在某些题目中会超时。那么我们需要做一个预处理,它的时间复杂度为O(nlog(n)),即为查询最值的ST表,查询时间复杂度O(1)。常数查询,是不是感觉非常的快。st表初始化后并非可以查询任意区间的最值,只能直接查询[1,2]、[2,3]...

2019-08-13 16:32:14

POJ2082解题报告(单调栈 矩形面积)

题意:柱状图是由一些长方形下端对齐后横向排列得到的图形。给一排高度不同底部在同一水平线的连续矩形,在形成的总区域内寻找面积最大的矩形子区域。现在有由n个宽度分别为wi,高度分别为hi的长方形从左到右依次排列组成的柱状图。问里面包含的长方形的最大面积是多少。维护一个栈中元素高度单调递增的栈,初始化栈中第一个元素高度宽度均为0,然后每次读入一个矩形,若它比栈顶元素还高就直接进栈,否则不断将栈中...

2019-07-04 13:08:21

POJ1029题解(穷举,假设检验)

题意:已知n个硬币中有且仅有一个假币,假币重量有问题,其余的都相同。给定n个硬币(编号从1到n),给定k次天平比较状态和结果。先要求根据这k次天平比较状态判断出哪个硬币是假币。若可以判断出来则输出该硬币编号,否则输出0。例如:输入如下5 3 (5表示有5个硬币,3表示称了3次,下面依次是每次称的结果)2 1 2 3 4 (2表示天平的左...

2019-07-02 23:15:34

POJ3269曼哈顿问题分析(穷举)

Problem DescriptionAfter scrimping and saving for years, Farmer John has decided to build a new barn. He wants the barn to be highly accessible, and he knows the coordinates of the grazing spots...

2019-07-02 17:23:00

POJ1061青蛙的约会 解题报告(扩展欧几里得妙用)

题意:两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐...

2019-07-02 16:23:45

POJ1700渡河 解题报告(贪心、模拟)

题意:一天夜晚,有n个人想渡河,每个人的渡河时间都不一样,每次只允许一个或两个人渡河,其中一个人需要拿着手电筒。问多久所有人才能成功渡河?分析:假设n个人的渡河时间从小到大分别为spend[1]、spend[2]。。。spend[n-1]、spend[n]当n==1时,渡河时间Sum_time=spend[1];当n==2时,渡河时间Sum_time=spend[2];当n==3时,渡河时...

2019-07-01 18:07:37
勋章 我的勋章
  • 技术圈认证
    技术圈认证
    用户完成年度认证,即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv1
    勤写标兵Lv1
    授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。