采石子
题目来源
本题由poj1042（或zoj1161）改编而来，是一道经典的贪心题目，在刘汝佳的“黑书” 上面有讲解。
解析
本题乍看像是动态规划，因为小A的终点不确定，似乎不能采用贪心法。但换一种方法想想，我们可以枚举小A的终点，那么在路上花的时间就可以直接从总时间中减去。因此我们可以采用贪心法的方法，每次在当前的石子量中选一个最大的。
另外，还应该注意输入输出格式以及细节处理的问题。
山洞历险
问题简化
我们可以将问题抽象为连续抛一枚硬币，连续出现两次正面即停止试验，求抛n次停止的概率。
解析
基于本题的数据规模，如果采用模拟，仅能解决10%-30%的数据。
解决本题一种比较快的方法是用模拟找出n<=10的概率，通过比较你会发现概率的分母就是2^n而概率的分子就是斐波那契数列的第n-1项。
找出本题的通项后用高精加与高精乘解决就可以了。（注意细节）。
以下是对该题的详细证明
投掷n次，每次有两个结果（正或反），故有2^n种情况。设满足n次停止的情况有Bn种，则Pn=Bn/2^n。
考虑投掷n+2次停止的情况，若第一次投出反面，则问题转化为投n+1次的情形；若第一次投出正面，那么第二次必为反面（否则两次已停止），则问题转化为投n次的情形。
∴P(n+2)=1/2*P(n+1)+1/2*1/2*P(n)
∴B(n+2)/2^(n+2)=B(n+1)/2^(n+2)+B(n)/2^(n+2)
∴B(n+2)=B(n+1)+B(n)
因此，该概率的分母为2^i，分子为斐波那契数列。
魔域之战
题目大意
一共有p种类型的格子，第一次进入需要花费代价（以后再进入就不需要了），同种类型的格子之间连通，求走出矩阵的最小代价。
解析
将题目简化后，我们可以想一下这几个条件：
1、同种格子连通，那么可不可以将同一种格子看成是一个点呢？（答案是肯定的）
2、又因为相邻的格子之间可以相互到达，那么对于这相邻的格子连通问题就可以转化为点与点之间存在路径的问题，因此我们将相邻的点建立联系。
3、基于前两点的模型转化，要求最小的代价，我们就可以用经典的最短路算法。
（另外要注意预处理、边界条件及空间复杂度）
荒山突围
题目简化:
有很多小屋，在这些小屋之间可能有道路相连。求最少可以在几个小屋中放置警卫而使所有的道路都能被警卫看到。（i点的警卫可以看到与i相连的所有道路）
本题实质：
树形DP经典版（“警卫安排”的简化版，只是在题目描述上。。。）
状态转移方程：
F[i,0]=sum(f[j,1]);
F[i,1]=sum(min(f[j,0],f[j,1]))+1;(i与j相连)
对状态转移方程的解释：
F[i,0]表示在当前节点i不放置警卫；F[i,1]表示在当前节点i放置警卫。对于一个节点i来说，它与其周围所有与它相连的节点j都有一条边e[i,j]；而对于这条边e[i,j]，或者它被i看到(即要在i点放置警卫f[i,1]+1+min{f[j,0],f[j,1]})，或者它被j看到(即要在j点放警卫f[i,0]+f[j,1])。
根据以上思路编写程序就很简单了，不过还要注意细节（比如这是一片不连通的森林等）。
题目来源
本题由poj1042（或zoj1161）改编而来，是一道经典的贪心题目，在刘汝佳的“黑书” 上面有讲解。
解析
本题乍看像是动态规划，因为小A的终点不确定，似乎不能采用贪心法。但换一种方法想想，我们可以枚举小A的终点，那么在路上花的时间就可以直接从总时间中减去。因此我们可以采用贪心法的方法，每次在当前的石子量中选一个最大的。
另外，还应该注意输入输出格式以及细节处理的问题。
山洞历险
问题简化
我们可以将问题抽象为连续抛一枚硬币，连续出现两次正面即停止试验，求抛n次停止的概率。
解析
基于本题的数据规模，如果采用模拟，仅能解决10%-30%的数据。
解决本题一种比较快的方法是用模拟找出n<=10的概率，通过比较你会发现概率的分母就是2^n而概率的分子就是斐波那契数列的第n-1项。
找出本题的通项后用高精加与高精乘解决就可以了。（注意细节）。
以下是对该题的详细证明
投掷n次，每次有两个结果（正或反），故有2^n种情况。设满足n次停止的情况有Bn种，则Pn=Bn/2^n。
考虑投掷n+2次停止的情况，若第一次投出反面，则问题转化为投n+1次的情形；若第一次投出正面，那么第二次必为反面（否则两次已停止），则问题转化为投n次的情形。
∴P(n+2)=1/2*P(n+1)+1/2*1/2*P(n)
∴B(n+2)/2^(n+2)=B(n+1)/2^(n+2)+B(n)/2^(n+2)
∴B(n+2)=B(n+1)+B(n)
因此，该概率的分母为2^i，分子为斐波那契数列。
魔域之战
题目大意
一共有p种类型的格子，第一次进入需要花费代价（以后再进入就不需要了），同种类型的格子之间连通，求走出矩阵的最小代价。
解析
将题目简化后，我们可以想一下这几个条件：
1、同种格子连通，那么可不可以将同一种格子看成是一个点呢？（答案是肯定的）
2、又因为相邻的格子之间可以相互到达，那么对于这相邻的格子连通问题就可以转化为点与点之间存在路径的问题，因此我们将相邻的点建立联系。
3、基于前两点的模型转化，要求最小的代价，我们就可以用经典的最短路算法。
（另外要注意预处理、边界条件及空间复杂度）
荒山突围
题目简化:
有很多小屋，在这些小屋之间可能有道路相连。求最少可以在几个小屋中放置警卫而使所有的道路都能被警卫看到。（i点的警卫可以看到与i相连的所有道路）
本题实质：
树形DP经典版（“警卫安排”的简化版，只是在题目描述上。。。）
状态转移方程：
F[i,0]=sum(f[j,1]);
F[i,1]=sum(min(f[j,0],f[j,1]))+1;(i与j相连)
对状态转移方程的解释：
F[i,0]表示在当前节点i不放置警卫；F[i,1]表示在当前节点i放置警卫。对于一个节点i来说，它与其周围所有与它相连的节点j都有一条边e[i,j]；而对于这条边e[i,j]，或者它被i看到(即要在i点放置警卫f[i,1]+1+min{f[j,0],f[j,1]})，或者它被j看到(即要在j点放警卫f[i,0]+f[j,1])。
根据以上思路编写程序就很简单了，不过还要注意细节（比如这是一片不连通的森林等）。
