USACO 3.4.2 American Heritage 解题报告
算法本质：树的遍历性质和深搜 算 法：先从中序遍历找出哪一个是根，即在先序遍历中下标最小的那个节点，这个节点向左就是左子树，向右就是右子树。 复杂度：空间&时间O(n) / LANG:C ID: yylgoo1 PROG: heritage / #include #include[......]
OI路程
SGU 103 Traffic Lights 解题报告
算法本质：单源最短路径+简单变形 算 法： 就是单源最短路径，我使用的SPFA，但是和普通单源最短路径不同的是，这个需要把路上所消耗的时间加上等待两边的灯同时亮起的时间这样唯一要耽误点时间实现的就是计算等待的时间。 计算在时间k通过a,b两个路口所需要等待的时间算法如下，如果此时（k）a，b[……]
USACO 3.3.5 A Game 解题报告
本质：动态规划 算法：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"[……]
USACO 3.3.4 Home on the Range 解题报告
题目本质：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][……]
USACO 3.3.3 Camelot 解题报告
题目本质：模拟+枚举 算 法： 首先，将国王与每个点的所需要的步数枚举出来，然后再对每个其实分别枚举，枚举每个点的步数，如：dist[i][j][0]代表将当前这个骑士移动到i,j所需要的步数，dist[i][j][1]代表当前这个其实和国王相聚在i,j总共的步数（包括国王走的步数。），dis[……]
USACO 3.3.2 Shopping Offers 解题报告
这题我折腾了三天，一直在考虑怎么排除这种情况，怎么考虑到那种情况，虽然我想得到是DP，也是正确的方程，但是我也不知道怎么那么多现在觉得傻里傻气不需要考虑的问题，反正好傻就是，其实方程就是F[a1][a2][a3][a4][a5]=min{F[ a1-P[i][1] ][ a2-P[i][2] ][[……]
USACO 3.3.1 Riding The Fences 解题报告
应该说比较明显吧，一个欧拉路径，其实为什么能这么实现一个欧拉路径我自己都还没想清楚，更别指望我说的清楚，看着标程写的代码，唉，不算抄袭但也确实没理解为什么能这样，反正这就是一个欧拉回路的实现，代码如下： 晚点发上来，在Fedora里面。 2011-01-29 17:19 代码: de la[……]