三帅锅_贪心方法和动态规_

《三帅锅_贪心方法和动态规_》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、-38-1037, 最短网络（AC/Submit）1229/3207Problem：农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。Input：该题含有多组测试数据。第一行为M表示有M组测试数据。每组数据第一行为农场的个数，N（3<=N<=100）。接下去为一个N*

2、N的矩阵,表示每个农场之间的距离。(农场之间的距离小于100000)Output每组数据只有一个输出，其中包含连接到每个农场的光纤的最小长度。SampleInput140492140817980162117160SampleOutput28解题思路：典型的dijstrala算法。-38-代码如下：#include"stdio.h"#definemax100001inttotal,a[101][101],tag[101],MIN[101];voidklus(intn)//从第一个结点开始{inti,j,s,min;total=0;for(

3、i=1;i<=n;i++)tag[i]=0;//标志都没添加进去tag[1]=1;//从第一个村庄开始for(i=2;i<=n;i++)MIN[i]=a[1][i];MIN[1]=a[1][1];for(i=2;i<=n;i++)//将n-1个村庄都添加进去{min=max;for(j=2;j<=n;j++)if(tag[j]==0&&MIN[j]

4、a[s][j]0){scanf("%d",&N);for(i=1;i<=N;i++)for(j=1;j<=N;j++)scanf("%d",&a[i][j]);klus(N);printf("%d",total);}return0;}1111, 勇闯黄金十二宫……双鱼宫（AC/Submit）833/

5、2196Background话说星矢、紫龙、冰河、阿瞬为了救活雅典娜，必须勇闯黄金十二宫。Problem最后一个他们来到双鱼宫，身为双鱼座黄金圣斗士的阿布罗狄被人称为最美丽、最漂亮的圣斗士，他的武器就是一些毒玫瑰花。然而紫龙和冰河在前面两个宫的战斗中已经牺牲了，而阿瞬为了要让星矢能快点到达教庭，他一个人留下来和阿布罗狄单挑。由于阿布罗狄的毒玫瑰花粉可以扩散，阿瞬的锁链旋转星云阵就防不住了。于是他脱下圣衣，要使出他的绝强招术:-38-星云旋风。不过阿瞬发星云旋风只能发一段时间，但是可以发很多次。已知现在阿瞬可以发n次星云旋风，每次攻击有一

6、个起始时间Si和一个结束时间Fi（Si<=Fi），但是一旦选中一次攻击就必须全部攻击完，中途不能停止，而且必须从起始时间开始。因为每次的攻击效果相同，所以当然是次数越多越好，问阿瞬最多可以攻击多少次。最后阿瞬打败了阿布罗狄，但是他也被阿布罗狄的玫瑰花吸干了血。（后来又被雅典娜救活了，那是后话。）星矢也成功地到达教庭，救活了雅典娜，并且打败了假教皇，双子座的撒加。Input本题包含多组数据.第1行，为n(1<=n<=500)下面n行，每行2个数字，为Si,Fi，0<=Si<=Fi<=32767,表示第i次攻击的起始时间和结束时间。Outp

7、ut对于每组数据输出一行，为最多攻击次数。SampleInput3020113SampleOutput2解题思路：贪心法，先按结束时间非减来对这些数据排序，然后再按最小结束时间优先来选择。代码如下：#include"stdio.h"inta[501][3];voidsort(intn){-38-inti,j,c;for(i=1;ia[j+1][2]){c=a[j][1];a[j][1]=a[j+1][1];a[j+1][1]=c;c=a[j][2];a[j][2]

8、=a[j+1][2];a[j+1][2]=c;}}intmain(){inti,j,count,end,n;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++)scanf