USACO 3.4.3 Electric Fence 解题报告
题目本质:相似三角形+枚举 算法描述:题目给出的三角形比较特殊,所以可以直接枚举,当然也不能说是直接枚举咯。我的算法是,对于每一行进行枚举,但是很快就到瓶颈了,无法确定坐标,虽然能够画出相似三角形,因为三角形的一条边在x轴上,所以从y等于(-)1(看情况而定是1还是-1)至m,每一行做与x轴平行的线[……]
题目本质:相似三角形+枚举 算法描述:题目给出的三角形比较特殊,所以可以直接枚举,当然也不能说是直接枚举咯。我的算法是,对于每一行进行枚举,但是很快就到瓶颈了,无法确定坐标,虽然能够画出相似三角形,因为三角形的一条边在x轴上,所以从y等于(-)1(看情况而定是1还是-1)至m,每一行做与x轴平行的线[……]
本 质:动态规划 算法描述:f[i][j] = max(f[i – 1][j – 1] + num[i][j], f[i][j – 1]) 方程十分简单,但是我久久不能AC,看了别人的代码也没看懂为什么初始需要f[i][i] = f[i – 1][i – 1] + num[i][i] [……]
算法本质:树的遍历性质和深搜 算 法:先从中序遍历找出哪一个是根,即在先序遍历中下标最小的那个节点,这个节点向左就是左子树,向右就是右子树。 复杂度:空间&时间O(n) / LANG:C ID: yylgoo1 PROG: heritage / #include #include[......]
算法本质:单源最短路径+简单变形 算 法: 就是单源最短路径,我使用的SPFA,但是和普通单源最短路径不同的是,这个需要把路上所消耗的时间加上等待两边的灯同时亮起的时间这样唯一要耽误点时间实现的就是计算等待的时间。 计算在时间k通过a,b两个路口所需要等待的时间算法如下,如果此时(k)a,b[……]
本质:动态规划 算法:f[i][j]代表从(i, j)能取的最大值,sum[i][j]代表它们的总和 f[i][j] = sum[i][j] – min(f[i + 1][j], f[i][j – 1]); 复杂度: 时间&空间:O(N^2) de lang="c"[……]
题目本质:DP 算法: 这题怎么说吧,我是想了好久没想出来,看了下别人的提示,天啊~好简单,DP方程如下: f[i][j]代表以i,j为左上角的正方形的边长大小,那么f[i][j] = min(f[i][j], f[i + 1][j], f[i][j + 1], f[i + 1][j + 1][……]
题目本质:模拟+枚举 算 法: 首先,将国王与每个点的所需要的步数枚举出来,然后再对每个其实分别枚举,枚举每个点的步数,如:dist[i][j][0]代表将当前这个骑士移动到i,j所需要的步数,dist[i][j][1]代表当前这个其实和国王相聚在i,j总共的步数(包括国王走的步数。),dis[……]