这是第二次模拟测试的解题报告
本次题目出自OIBH模拟赛

题目如下：
===================================================================================================================
饮食问题
（eatpuz.pas/c/cpp/in/out）
时限:1 sec | 内存: 64 MB

背景
     平平正在减肥，所以要控制他的饮食。并且要求她及时去公园里面散步。
题目描述
平平正在减肥，所以她规定每天不能吃超过 C (10 <= C <= 35,000)卡路里的食物。农民 John 在戏弄她，在她面前放了B (1 <= B <= 21) 捅食物。每桶内都有某个单位卡路里(范围：1..35,000)的食物(不一定相同)。平平没有自控能力，一旦她开始吃一个桶中的食物，她就一定把这桶食物全部吃完。
平平对于组合数学不大在行。请确定一个最优组合，使得可以得到最多的卡路里，并且总量不超过C。
例如，总量上限是40卡路里， 6 桶食物分别含有7, 13, 17, 19, 29, 和 31卡路里的食物。平平可以吃7 + 31 = 38卡路里，但是可以获取得更多： 7 + 13 + 19 = 39卡路里。没有更好的组合了。

输入
共两行。
第一行，两个用空格分开的整数： C 和 B
第二行，B个用空格分开的整数，分别表示每桶中食物所含的卡路里。

输出
共一行，一个整数，表示平平能获得的最大卡路里，使她不违反减肥的规则。

输入样例
40 6
7 13 17 19 29 31

[样例输出]
39

三个袋子
（bags.pas/c/cpp/in/out）
时限:1 sec | 内存: 64 MB
背景
    平平在公园里游玩时捡到了很多小球，而且每个球都不一样。平平找遍了全身只发现了3个一模一样的袋子。他打算把这些小球都装进袋子里（袋子可以为空）。他想知道他总共有多少种放法。

题目描述
    将N个不同的球放到3个相同的袋子里，求放球的方案总数M。
    结果可能很大，我们仅要求输出M mod K的结果。
    现在，平平已经统计出了N<=10的所有情况。见下表：
N 1 2 3 4 5 6 7 8 9 10
M 1 2 5 14 41 122 365 1094 3281 9842

输入
两个整数N,K，N表示球的个数。

输出
输出仅包括一行，一个整数M mod K 。

输入样例 ( bags.in )
11 10000

输出样例( bags.out )
9525

数据规模
对于 40%数据,10<=N<=10,000
对于100%数据,10<=N<=1,000,000,000
对于 100%数据，K<=100,000

智捅马蜂窝
（clever.pas/c/cpp/in/out）
时限:1 sec | 内存: 64 MB
背景
    为了统计小球的方案数，平平已经累坏了。于是，他摘掉了他那800度的眼镜，躺在树下休息。
    后来，平平发现树上有一个特别不一样的水果，又累又饿的平平打算去把它摘下来。
题目描述
    现在，将大树以一个N个节点的无向图的形式给出，每个节点用坐标（Xi，Yi）来表示表示，平平要从第一个点爬到第N个点，除了从一个节点爬向另一个相邻的节点以外，他还有一种移动方法，就是从一个节点跳下，到达正下方的某个节点（之间可隔着若干个点和边），即当Xj=Xi and Yi<Yj 时，平平就可以从j节点下落到i节点，他下落所用时间满足自由落体公式，t=sqrt((Yj-Yi)*2/g) （注意：g取10）。如果出现两线相交的情况，我们不认为它们是相通的。

输入
两个整数N,V，N表示节点个数，V表示平平爬树的速度。
接下来N行，每行包含3个整数X,Y,F，X,Y是这个点的坐标，F是他的父节点（F一定小于这个点的标号，第一行的F为0）。
注意：两节点间距离按欧几里德距离计算 dis = sqrt( ( x1 – x2 ) 2+ ( y1 – y2 )2 )

输出
输出仅包括一行，从1到N所用的最少所需时间T，保留两位小数。

输入样例 ( clever.in )
9 1
5 0 0
5 5 1
6 5 2
7 6 2
6 9 2
3 6 2
4 5 2
3 2 7
7 2 3

输出样例 ( clever.out )
8.13

数据规模
对于100%数据,1<=N<=100,1<=V<=10,0<=X,Y<=100.
建议使用extended(pas)或double（c and c++）计算，我们对于精度造成的误差将不予重测。

过河
（river.pas/c/cpp/in/out）
时限:1 sec | 内存: 64 MB
背景
    经过一番努力，平平终于摘到了水果，拿近一看才发现是马蜂窝。
    平平从树上掉了下来，没命的跑啊跑啊……
    后来，他发现前方有一条河。现在他用电话求助于你，希望你在他跑到之前铺好过河的路，让他顺利过河。

题目描述
    已知河的长度为L，现在我们有M个石子，我们可以把一个石子铺在河上的一个点，让平平踩着这些石头过河。河上已经有N个石子，而且已知平平每步跨出的距离为S到T之间的整数（ S <= T ），起点是0点，河为1到L，只要平平最后能跳过L（必须大于L）就算平平顺利过河。
    如果平平能够过河，请输出最少步数，否则输出最远到达的距离，以便我们及时去救起平平。

输入
第一行有五个整数L,N,M,S,T ，L是河的宽度，N表示河里原来就有N个石头，M表示我们手上拥有的石头，S,T表示平平的一步最小的跨度和最大跨度。接下来N行有一个值表示在河里的石头的位置（从小到大给出）。

输出
输出仅包括一行，如果能够过河，输出最少步数，否则输出平平能够到达的最远距离。

输入样例 ( river.in )
样例1：
8 2 2 2 3
2
3

样例2：
10 1 1 1 2
2

输出样例 ( river.out )
样例1：
3

样例2：
4

数据规模
对于40%数据,1<=M<=L<=1000 , 1<=S<=T<=10 ;
对于100%数据,1<=M<=L<=100000;
对于100%数据,1<=S<=T<=100,1<=N<=100.

后记
    可怜的平平还是没有逃过被马蜂蛰的命运。大老板以最快的速度把平平送到了医院。
平平的故事就此告一段落。现在平平小朋友正躺在家里好好休息，准备冲刺2007年的NOIP……
================================================================================================================

解题报告：

第一题：
            简单的01背包，就算使用回溯法枚举所有可能情况也能过（经测试），数据很弱。。。。。。。
            本人用DP方法，求出了所有可能得到的卡路里值
            附上程序：

 
第二题：
            无奈的数学题，快速幂，或者干脆用矩阵乘法加速，看着办吧

第三题：
            简单的单元最短路，注意如果可能掉下来而不用爬的方法，更新两点间的通路时间，其他没什么了。
            Dijkstra算法，代码： 

第四题：
            让人崩溃的DP题目，不过由于数据比较弱，搜索应该也是可以过的（不过本人不会）。

            首先我们应该明确题目中的几个重要部分（或者说是细节步骤，要不然就是过河时的一般规律）：
            1、如果可能到达河岸对面，那么，手中的石头全部使用完肯定对应至少一个最优解（为什么？自己想，简单的很）；
            2、对于两个石头之间，是否存在可能到达方式的判断条件：len/s*t>=len（len为两石头间的距离，下同）  (具体证明，可以形象的画一画）；
            3、如果两个点（或者说石头），如果之间有可能的方法到达（即满足2中的判断条件），那么，从一个石头到达另一个石头所需要踩过的其他石头（即非这两个石头）的数目为 (len-1)/t,并且可以保证一定有这样子的一种到达方法。

            接下来，就应该介绍动态转移方程，以及相关的预处理了。
            对于数据，我们首先要进行一些必要的预处理：
            1、对于读入的每个石头的位置，通过对于上述条件的判断，如果从0点不可到达，则可以将次石头略去不考虑；
            2、因为题目要求一定要过河（就是行动的总距离要大于L才行），所以就在 L+1~L+S 这S个位置上人为的构造出S个石头，并认为这些石头是本身存在与河面上的。
            3、对于上面提到的每一个石头，应该对其预处理出一个值（我将其保存在B数组中），代表从0点到达这个石头中间要踩过多少个石头（这里踩过的石头可以是已有的，可以是从手中放下的，石头数允许是不合法的。注意：这个数组只是表示这一种可能情况，不表示一定满足输入数据）；
            4、动态规划的初始状态 F[i][0]=b[i]+1。

            接下来，介绍动态规划中状态的表示方法：
            F[i][j]表示从0点到第i个石头，中间如果踩过j个石头，所需要的最少步数。（注意：此处是踩过，如果只是经过某个石头而不必踩过，则这个石头就不包含在这j个石头中）。

            动态转移方程：
            F[j][k+ifneed(i)]=min{F[i][k]+w[i][j]+1} (0<=k<i),其中w[i][j]表示从第i个石头到第j个石头中间要踩过的石头数，ifneed表示一种判断条件，就是用来判断如果到达第j个石头,是否一定要踩到第i个石头上面,如果必要,则返回1,否则返回0。具体的判断方法实现如下：


            最后就是对结果的判断了。

            第一项，应该是判断是否存在能够过河的方法。由于可以明显的看出，在上述动态规划的过程中，由于判断了中转石头是否必要踩过，已经形成了一定的贪心规则。所以，在输出时，就应该对最后s个石头（就是自己加进去的石头判断），如果b[i]满足条件，就取其中最小的；如果b[i]>m，就取F[i][b[i]-m]里最小的。（原因应该很简单，因为上面在转移和预处理时已经保证了得到最优）
            第二项，就是在第一项没有找到过河步数是，求出最远走到哪里了。这里就更为简单了：1、最近可以走m*t的距离；2、如果F[i][j]可行（就是不为0），并且满足m+j>=b[i]，就判断rock[i]+(m+j-b[i])*t 是否为可行解即可。
            
            再来分析一下时间复杂度，由于石头数不大于100，s也不大于10，对于上述O(N^3)的算法是绝对不会超时的。这样，这道题就完美解决了。

附上代码：