算法青蛙过河.doc

吉林财经大学课程设计报告所在院系：信息学院计算机系科目名称：算法设计与分析学号：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问题描述在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。对于30%的数据，L=10000对于全部的数据，L=109输入格式 Input Format输入的第一行有一个正整数L（1 = L = 109），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 = S = T = 10，1 = M L，那么map中stonei和stonei-1两石头的距离就被等效成为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=TLKK=1;p=p+K;mapp=1i=0;fjmin j = iNYi=p；fiLCM时情况与相距 LCM+(S MOD LCM)情况一样dp就很简单了dpi表示跳到i个位置（压缩后的）最少踩到的石子数则有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 #include 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 temp)j-;if (i j)stonei = stonej;i+;while (i j & stonei temp)i+;if (i 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, 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 = 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，在该居民点设置服务机构的费用为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个整数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个点）也是最优的。我们引入数组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=kinTempcur+=ri.c;j=prev+1jiYNdepth=0|(depth!=0&ri.x+rprev.xrj.x*2)tempcur+=(ri.x-rj.x)*rj.w;j=i+1tempcur+=(rj.x-rprev.x)*rj.w;jntemp+=(rj.x-ri.x)*rj.w;tempcur+tempansans=tempcur+temp;dfs(depth+1,i,tempcur);i+;j+2.4复杂性分析根据递推公式，容易求出c0k+1的递推式。时间复杂度为O（nlog2n）。2.5总结设xt是增设的第一个服务站，总的服务费用等于x1xt-1到x0的服务费用W1加上后面一段xtxn增设k个服务站的费用W2是最优的。证明使用反正打，如果这后面一段服务费用W2不是最优的，假设存在某种增设方法得到后一段服务费用W2W2，则W2-W1W2-W1，所以得到原来的设置方法不是最优解，这与题设矛盾，所以后面一段必须是最优的。2.6附录#include 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;in;i+) int temp=0,tempcur=cur; tempcur+=ri.c; for(j=prev+1;ji;j+) if(depth=0|(depth!=0&ri.x+rprev.xrj.x*2)tempcur+=(ri.x-rj.x)*rj.w; else tempcur+=(rj.x-rprev.x)*rj.w; for(j=i+1;jn;j+) temp+=(rj.x-ri.x)*rj.w; if(tempcur+tempans)ans=tempcur+temp; dfs(depth+1,i,tempcur)