我的USACO总结Congratulations!You have finished all available material.Chapter1DONE2008.12.16Getting startedChapter2DONE2008.12.24Bigger ChallengesChapter3DONE2009.01.15Techniques more subtleChapter4DONE2009.02.03Advanced algorithms and difficult drillsChapter5DONE2009.02.17Serious challengesChapter6DONE2009.02.20Contest Practice花了差不多四个月把USACO做完了，感觉收获很大，它就像一个私人教练能督促你学习一样，对于一个oier来说，USACO绝对是一个不可不做的经典OJ，为了整理一下知识点也当是一次巩固，便写下了这篇总结，以总结一下自己的疏漏，也希望能帮助到别人。
--湖南南县一中czz一、枚举枚举是我们用的比较多的一种算法，编程简单是它的优点，而时间效率低则是它的致命缺点，不过很多题目通过合理的优化比如减小枚举量等来优化算法。
The Clocks是第一道需要优化的枚举题，首先由于这题有9个时钟，而且每个的移动次数也不清楚，似乎无从开始，不过经过研究发现对于一个时钟如果移动四次就会便相当于没有移动，因此我们只需要枚举每个钟的四种状态共9^4共6561种状态，这样就不会超时了，不过如果进一步研究这个题目发现移动方案之间是有约束的，打个比方，A时钟由三种移动方案确定，如果其中的两种方案的次数已经知道，那么第三种方案也就会确定，因此我们只要枚举前三个方案的次数其他的便可以递推出来，状态只有4^3个，效率无疑大大提高。
Arithmetic Progressions这题由于题目要求按b升序排列，所以我们习惯性得把b放在外循环而a放在内循环，这样做加上剪枝后也会超时，由于剪枝时按a 剪枝时力度无疑会更大，因此我们可以把a提到外循环，相应的加一个快排，因此我们得出一个结论：把剪枝有利的尽量放在外循环。
素数的题目也有几个，枚举就行了，不过注意要先生成一定范围内的素数，然后再枚举判断，不过有一种随机化的素数判断可以在klogn内判断，可以参考周咏基的论文《论随机化原理与设计》。
Party Lamp与The Clocks有异曲同工之妙，同样我们可以判断出一个按钮如果按了两次就没有意义了，n值是有小于4时才会限制按键次数否则不予考虑。
不过这样枚举还是会超时，如果再次分析可以发现每六个灯一个循环即灯的最后状态是循环的，因此只要枚举6个灯的状态即可，算法十分优秀了。
Controling Company当时看到这道题时，看到题解是才发现N的范围并不大，完全可以用迭代枚举来求解，即不断枚举更新公司之间的关系，直到无法更新。
可以看出枚举对付一些看起来很复杂的题目很有一套。
Contact也是一道难题，为了判重，我们不得不借助于Hash表，把一个字符串看出一个二进制数，不过为了区分11和0011这样的相同大小的字符串，我们可以先处理长度为1的，再处理长度为2的……知道处理完全。
Camelot应该是USACO里最难的一道枚举题目，首先我们可以用广搜得到棋盘之间的最短路径，然后先枚举汇合点，再枚举汇聚点，最后枚举接国王的骑士，不过这样超时十分严重，继续分析，由于国王走路很慢，因此肯定要让他尽量少走路，我们可以进一步缩小汇聚点的范围，即在国王两部以内，这样就AC 了由此可以看出枚举的一般思路：1、估计枚举量，看是否可行。
2、确定枚举对象，注意把容易剪枝的放在外面。
3、进一步分析看可否减小枚举量(注意挖掘枚举对象之间的约束关系)。
二、动态规划USACO离的动态规划题是比较多的，主要分为几类：1、背包问题Subset sums是一道典型的01背包问题模型，由于它要求求出均等划分的个数，对于奇数的总和特判无解，因此先用动态规划求出装出总重量的一半，由于集合的对称性，即N=3时，{1,2}和{3}是同一中方案，因此将结果除以2即是答案。
Money System，Score Inflation则是完全背包模型，由于物体个数无限，所以我们在实现时只要将一维数组的实现循环倒过来即可。
Stamps是背包问题的变种，不过颇为简单，设can[i]表示i容量能否装出，则can[i]=can[i]or can[i-w[k]]。
Shopping Offers也是dp，不过从一维到了五维，而且实现时要把物体的编号映射为1..5，方便处理。
不过这题有个相当有趣的图论算法：构图，每种购买商品的组合是一个顶点，每种打折方式是一条边，然后SPFA求解。
Beef Mcnuggets是一道有难度的dp，由于题目的范围巨大，直接dp是肯定MLE+TLE，不过我们进行一下数学分析就会发现，题目中的数据是吓人的，如果数据中任意两个数不互质，那么无法装出来的数一定小于最大的两个数的最小公倍数。
此时便可以进行dp了，此题体现了数学分析在信息学奥赛中的作用。
Milk Measureing开始做的时候用的ID迭代加宽搜索+DP,结果由于数据暴弱，竟然过了，但是我在网上找了很久也没有找到纯DP的题解，不知那位大牛可以指教一下。
Raucous Rocker也是一个类背包问题，我们设f[i,j]表示前i张光盘放前j首歌时最多放的个数，那么决策就是第i张光碟放多少，得出方程：F[i,j]=Max(f[i-1,k]+g[k+1,j]);其中g[i,k]表示将第i到第k首歌放在一个光盘中最多放的个数，对于g数组我们可以将数组排序后从左到右扫描即可（可以增设Order[i]表示现在第i个数原来的位置）。
复杂度为O(n^2*m)，完美解决了这个问题。
2、与矩形边长有关问题主要有三个问题：Home on the rage Big barn A rectangular Barn其中前两个问题较为简单，用f[i,j]表示以第i行第j列为右下角时最大正方形的边长，则f[i,j]=min(f[i-1,j-1],f[i-1,j],f[I,j-1])+1;即往上面，左边，左上三个方向扩展的最大长度最小值为现在的最大扩展边长。
第三个题目由于是求矩形面积，所以不能简单的套用以前的方程，这里我们设三个数组，L,R,H分别表示向左，向右，向上扩展的最大长度，则：H[i,j]=H[i-1,j]+1;L[i,j]=Min(L[i-1,j],J-最靠近的坏格子（左边的）)；R[i,j]=Min(R[i-1,j],最靠近的坏格子（右边的）)；由于会超空间，所以我们可以用数组迭代计算即可。
具体这个方程是怎么来的可以参考王之坤的论文。
3、求解第N个状态问题这种类型以Two Five和Stringsobits为代表，这类题目共同的特点是给定一系列规则构造出一系列对象，要你求第N个状态，而共同的求法就是利用动态规划求出每一位的总数，然后一位一位求解。
Stringsobits由于题目范围巨大，所以模拟是肯定TLE，考虑动态规划：设F[N,L]表示N个0和1组成的1个数小于等于L的数的个数，则F[N,L]=F[N-1,L-1]+F[N-1,L]//分别在前面加一个0和1{上面的方程和组合数的方程及其相似，可以结合理解}边界条件F[I,0]=1;F[0,I]=1;（0<=I<=N）;（注意利用小数据推边界条件）求出来以后我们一位一位处理，假设A[I]表示序列的第I位，对于每I为，如果F[I-1,L]<M，那么第I位为1，否则为0；核心代码：For I:=N downto1doIf F[I-1,L]<M Then Begin M:=M-F[I-1,L];L:=L-1;A[I]:=1;endElse A[I]:=0;Two Five一题与上题有异曲同工之妙，虽然我一下子就知道使用动态规划来确定每一位，不过方程颇难想到，只好看了星牛的题解，突然之间意识到：如果一位一位放，因为后面的数都比前面的数大，所以对于一个状态，其解的个数只与其“形状”有光，所以星牛的那种定义方法可行，至于具体由于我还没有理解透彻，就不多说了。
4、其他The Longest Prefix这题注意要整体定义，用Can[j]表示S[1..J]是否可以组成，那么Can[J]=Can[J-Len[i]]And(S[J-Len[i]+1..J]=Word[i]);由于前缀最大长度只有20，因此如果连续20无法得到，就可以结束算法，同时由于是基于字符串比较，我们可以用Trie来优化。
Cow Pedigrees一道有难度的dp，主要原因是因为我们的思想太僵化或者说固执，我刚开始定义F[i,j]表示节点数为I深度为J的个数，结果发现状态很不好转移，看了题解之后发现，只要定义F[I,J]表示节点数为I深度不超过J的个数，就很好进行转移了，所以我们定义状态后如果发现不好转移，可以考虑修改方程使得方程更加抽象，这样有利于转移。
Humble Numbers这题似乎不算动态规划，不过在求解的过程中也包含了动态规划的思想，即有前一个数退出下一个数，对于每一个数设置一个指针，如果这个数*指针所对于的数小于等于前一个数求指针加1，这样推n次皆可得到答案。
A Game是一道博弈型动态规划，对于博弈我还没有认真钻研过，不过还是说说对于这道题的理解：由于要对第二位选手也执行最优策略，所以符合最优化原理，我们设F[I,J]表示第一个取的选手（不一定是第一位选手）在I..J中取数时取得的最大值，Sum[I,J]表示I..J的和。
此时取得选手有两种决策：取最左边或最右边，此时由于要为另外一位选手也执行最优决策，如果取最左边，则F[I,J]=A[I]+(Sum[I+1,J]-F[I+1,J])//取得数+Sum[I+1,J]-另一位选手取的数综合起来，转移方程为：F[I,J]=Max(A[I]+(Sum[I+1,J]-F[I+1,J],A[J]+(Sum[I,J-1]-F[I,J-1])；注意认真体会上面的方程。
Canada Tower一题可以说是动态规划的鼻祖题，IOI97出了这一题，当时的选手没有一个了解动态规划，结果全部用的搜索，结果没一个人AC 了，回国后开始研究这种新算法，从此动态规划成为比赛的热点。
不扯了，说这道题，把问题转化一下，变为从1才是找到两条不相交的航线使得过的点最多，用F[I,J]表示从1开始，一条航线到I，一条航线到J时最多过的点数，则F[I,J]=Max(F[I,K]+1)满足（K<J且Map[K,J]=1）可能有人会问为什么这样得到的方程可以使得航线不相交，如果我们初始化F数组为Maxint，F[1,1]=1，然后第一步DP时就可以保证没有相交的航线，同样由于第一步没有，第二步也没有，因此不存在相交路线。