算法青蛙过河

1、吉林财经大学课程设计报告所在院系：信息学院计算机系科目名称：算法设计与分析学号：1401080940姓名：付为设计题目：题目一:过河问题题目二:直线k中值问题提交时间：2011年3月目录1、青蛙过河问题 11.1题目描述与设计要求 11.2问题分析 11.3算法设计 21.4复杂性分析 41.5总结 41.6附录 42、k中值问题 42.1题目描述与设计要求 72.2问题分析 72.3算法设计 82.4复杂性分析 92.5总结 92.6附录 9青蛙过河1.1问题描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳

2、过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。对于30%的数据，L<=10000对于全部的数据，L<=109输入格式 Input Format输入的第一行有一个正整数L（1 <= L <= 1

3、09），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。输出格式 Output Format 输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。样例输入 Sample Input102 3 52 3 5 6 7样例输出 Sample Output21.2问题分析路径压缩法，虽然桥很长，但上面最多只有100个石

4、子，想到能否用石子DP，而应该是不行的。由于石子排布非常的疏，我们还会发现，如果两个石子相隔甚远，那他们中间的fi大部分将会是同一个数，能否把两个石子的距离缩短，使之还与原来等效？要是行的话怎么缩？王乃岩同学考试时做了一个方法能够过全部数据，用的滚动数组存储，下面列出了他的程序。我自己也写了个程序，和他不尽相同：我令L=stonei-stonei-1（stonei代表按坐标由小到大顺序排列的石块坐标），当L能够被t整除时（L%t=0），令k=t；当L不能被t整除时（L%t!=0），令k=L%t。然后令k为k+t，最后判断如果k>L，那么map中stonei和stonei-1两石头的距离就

5、被等效成为L（也就是没变）；如果k<=L，那么map数组中stonei和stonei-1两石头的距离就被等效成为k，可以看出来，这样处理完，两石子最大间距为2*t，大大的缩短了数组，再按解一进行DP，就可以通过了。1.3算法设计J+P=0;i=1输入L,S,T,M;stonei,min=1000YNi<=Mmemset(map, 0, sizeof(int)*100001);memset(f, 0, sizeof(int)*100001);quickSort(1, M); l = stonei - stonei - 1;YNL%T=0K=l%T;K=K+TK=TL<KK=1;

6、p=p+K;mapp=1i<=p+Tj=i-Tj>=0;fj<min j <= iNYi<=p；fi<minMin=fj;fi=min+mapii=p+1 min = fi1.4复杂性分析简单动态规划，fi代表青蛙跳到i点时所可能踩到的最少石子数，所以有fi=minfk+mapi(i-ski-t)，其中mapi代表i上是否有石子，有是1，否则0。算法复杂度O(n2)。路径压缩的dp路径压缩方法：设s与t的最小公倍数为LCM,则当相邻的两粒石子距离S>LCM时情况与相距 LCM+(S MOD LCM)情况一样dp就很简单了dpi表示跳到i个位置（压缩后的

7、）最少踩到的石子数则有dpi=mindpi-j+fi 对于s<=j<=t当第i格有石子时fi=1否则fi=0我们不难发现其实这题可以应用单调队列（虽然没有必要）目前我的方法是用一个缓存队列保存i-s+1至i格的情况，每次将第i格算出后加入缓存，并将缓存中第i-s+1格入单调队列这样时间复杂度由O(n2)降至O(N)1.5总结这道题在没看数据规模之前以为是一道简单的DP，但是数据开到十亿，无论在时间还是空间复杂度都过大，所以就要进行优化了。选择简单的动态规划方法会使复杂度太高，所以我选择了路径压缩法，调用队列使复杂度大大降低。1.6附录代码#include <stdio.h&g

8、t;#include <string.h>long stone101;int map100001;int f100001;long L;int S, T, M; void quickSort(int l, int r)int i , j;long temp;i = l;j = r;temp = stonei;while (i < j)while (i < j && stonej > temp)j-;if (i < j)stonei = stonej;i+;while (i < j && stonei < temp)

9、i+;if (i < j)stonej = stonei;j-;stonei = temp;if (i - 1 > l) quickSort(l, i - 1);if (i + 1 < r) quickSort(i + 1, r);int main()int i, j;long l, k, p = 0, min;scanf("%ld%d%d%d", &L, &S, &T, &M);for (i = 1; i <= M; i+)scanf("%ld", &stonei);memset(map,

10、 0, sizeof(int)*100001);memset(f, 0, sizeof(int)*100001);quickSort(1, M);stone0 = 0;p = 0;for (i = 1; i <= M; i+)l = stonei - stonei - 1;if (l % T = 0) k = T;elsek = l % T;k = k + T;if (l < k)k = l;p = p + k;mapp = 1;for (i = 1; i <= p + T; i+)min = 1000;for (j = i - T; j <= i - S; j+)if

11、 ( j >= 0 && fj < min)min = fj;fi = min + mapi;min = 1000;for (i = p + 1; i <= p + T; i+)if (fi < min)min = fi;printf("%dn", min);return 0;直线k中值问题2.1问题描述在一个按照南北方向划分成规整街区的城市里，n个居民点分布在一条直线上的n个坐标点x1 << xn处。居民们希望在城市中至少选择1个，但不超过k 个居民点建立服务机构。在每个居民点处，服务需求量为w i ³ 0，在

12、该居民点设置服务机构的费用为c i ³ 0。假设居民点xi到距其最近的服务机构的距离为di ，则居民点xi 的服务费用为wi ´ di 。建立k 个服务机构的总费用为A+B。A 是在k 个居民点设置服务机构的费用的总和；B是n个居民点服务费用的总和。编程任务：对于给定直线L 上的n 个点x1 << xn ，编程计算在直线L 上最多设置k 处服务机构的最小总费用。数据输入：文件夹data中的各输入文件第1 行有2 个正整数n和k。n表示直线L 上有n 个点x1 << xn ；k 是服务机构总数的上限。接下来的n行中，每行有3 个整数。第i+1行的3个整

13、数xi , w i , c i ，分别表示相应居民点的位置坐标，服务需求量和在该点设置服务机构的费用。结果输出:将计算的最小服务费用输出到文件output.out。输入文件示例 输出文件示例kml0.in output0.out9 3 192 1 23 2 16 3 37 1 19 3 215 1 616 2 118 1 219 1 12.2问题分析本题是求最优解的问题，考虑用动态规划算法。在直线L上增设k处服务机构，设xt为我们增设的第一个服务机构，则问题转化为x0到x(t-1)的最小费用。我们计算x0到xn曾设k个（设置k+1个点）是最优的，必须xt到xn增设k-1（设置k个点）也是最优的

14、。我们引入数组cij表示最小服务转移费用，其中i表示直线L上点xi处已设置了i个服务机构，j表示在xi后面设置j处服务机构。我们的问题转化为求c0k+1。计算出所有两点之间的距离d(i,j),并计算出之间的服务转移费m(i,j).设L上有n个点，在点xi处已设置了服务机构，现在要xi后设置j个服务机构（包括xi那个），使得整体服务转移费用最小，根据地推公式，容易求出c0k+1的递推公式。Ans=2100000000;i=prev+1;temp=0;tempcur=cur2.3算法设计YNDepth=ki<nTempcur+=ri.c;j=prev+1j<iYNdepth=0|(de

15、pth!=0&&ri.x+rprev.x<rj.x*2)tempcur+=(ri.x-rj.x)*rj.w;j=i+1tempcur+=(rj.x-rprev.x)*rj.w;j<ntemp+=(rj.x-ri.x)*rj.w;tempcur+temp<ansans=tempcur+temp;dfs(depth+1,i,tempcur);i+;j+2.4复杂性分析根据递推公式，容易求出c0k+1的递推式。时间复杂度为O（nlog2n）。2.5总结设xt是增设的第一个服务站，总的服务费用等于x1xt-1到x0的服务费用W1加上后面一段xtxn增设k个服务站的费用

16、W2是最优的。证明使用反正打，如果这后面一段服务费用W2不是最优的，假设存在某种增设方法得到后一段服务费用W2<W2，则W2-W1<W2-W1，所以得到原来的设置方法不是最优解，这与题设矛盾，所以后面一段必须是最优的。2.6附录#include <stdio.h>struct res int x,w,c;FILE* fp;int n,k;int ans=2100000000;struct res r10;void dfs(int depth,int prev,int cur) int i,j; if(depth=k)return; for(i=prev+1;i<n

17、;i+) int temp=0,tempcur=cur; tempcur+=ri.c; for(j=prev+1;j<i;j+) if(depth=0|(depth!=0&&ri.x+rprev.x<rj.x*2)tempcur+=(ri.x-rj.x)*rj.w; else tempcur+=(rj.x-rprev.x)*rj.w; for(j=i+1;j<n;j+) temp+=(rj.x-ri.x)*rj.w; if(tempcur+temp<ans)ans=tempcur+temp; dfs(depth+1,i,tempcur); int main() int i; fp=fopen("kml0.in&qu