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

- 39 -1037 , 最短网络（AC/Submit）1229/3207Problem：农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。 约翰已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。 你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。 Input：该题含有多组测试数据。 第一行为M表示有M组测试数据。 每组数据第一行为农场的个数，N（3=N=100）。 接下去为一个N*N的矩阵,表示每个农场之间的距离。(农场之间的距离小于100000) Output每组数据只有一个输出，其中包含连接到每个农场的光纤的最小长度。 Sample Input140 4 9 214 0 8 179 8 0 1621 17 16 0Sample Output28解题思路：典型的dijstrala算法。代码如下：#include stdio.h#define max 100001int total,a101101,tag101,MIN101;void klus(int n)/从第一个结点开始int i,j,s,min;total=0;for(i=1;i=n;i+) tagi=0;/标志都没添加进去tag1=1;/从第一个村庄开始for(i=2;i=n;i+)MINi=a1i;MIN1=a11;for(i=2;i=n;i+)/将n-1个村庄都添加进去 min=max;for(j=2;j=n;j+)if(tagj=0&MINjmin)/表示未添加进去min=MINj;s=j;total=total+min;tags=1;MINs=0;for(j=1;j=n;j+)if(tagj=0&asj0)scanf(%d,&N);for(i=1;i=N;i+)for(j=1;j=N;j+)scanf(%d,&aij); klus(N);printf(%dn,total);return 0;1111 , 勇闯黄金十二宫双鱼宫（AC/Submit）833/2196Background话说星矢、紫龙、冰河、阿瞬为了救活雅典娜，必须勇闯黄金十二宫。 Problem 最后一个他们来到双鱼宫，身为双鱼座黄金圣斗士的阿布罗狄被人称为最美丽、最漂亮的圣斗士，他的武器就是一些毒玫瑰花。然而紫龙和冰河在前面两个宫的战斗中已经牺牲了，而阿瞬为了要让星矢能快点到达教庭，他一个人留下来和阿布罗狄单挑。 由于阿布罗狄的毒玫瑰花粉可以扩散，阿瞬的锁链旋转星云阵就防不住了。于是他脱下圣衣，要使出他的绝强招术:星云旋风。不过阿瞬发星云旋风只能发一段时间，但是可以发很多次。 已知现在阿瞬可以发n次星云旋风，每次攻击有一个起始时间Si和一个结束时间Fi（Si=Fi），但是一旦选中一次攻击就必须全部攻击完，中途不能停止，而且必须从起始时间开始。因为每次的攻击效果相同，所以当然是次数越多越好，问阿瞬最多可以攻击多少次。 最后阿瞬打败了阿布罗狄，但是他也被阿布罗狄的玫瑰花吸干了血。（后来又被雅典娜救活了，那是后话。） 星矢也成功地到达教庭，救活了雅典娜，并且打败了假教皇，双子座的撒加。 Input本题包含多组数据. 第1行，为n(1=n=500) 下面n行，每行2个数字，为Si,Fi，0=Si=Fi=32767, 表示第i次攻击的起始时间和结束时间。 Output对于每组数据输出一行，为最多攻击次数。 Sample Input30 20 11 3Sample Output2解题思路：贪心法，先按结束时间非减来对这些数据排序，然后再按最小结束时间优先来选择。代码如下：#include stdio.hint a5013;void sort(int n)int i,j,c;for(i=1;in;i+)for(j=1;jaj+12)c=aj1;aj1=aj+11;aj+11=c;c=aj2;aj2=aj+12;aj+12=c;int main()int i,j,count,end,n;while(scanf(%d,&n)!=EOF)for(i=1;i=n;i+)scanf(%d%d,&ai1,&ai2);sort(n);j=1;count=1;end=a12;for(i=2;i=end)count + ;end=ai2;printf(%dn,count);return 0;防御导弹1004Problem某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够达到任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在使用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 Input最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000的正整数） Output两个整数M和N。表示：这套系统最多能拦截 M 枚导弹，如果要拦截所有导弹最少要配备N套这种导弹系统。 Sample Input300 250 275 252 200 138 245Sample Output5 2算法： 动态规划源代码：#include #include int totalN = 0;int a30, b30;void init () /初始化int data;totalN = 0; /导弹总数while ( scanf ( %d, &data ) != EOF )a+totalN = data;b1 = 1;void cal (int k) /计算以第k颗导弹为未位的最长下降序列的元素个数int i,max;if ( k totalN ) /如果所有导弹都考虑完了，返回return;max = 1; /初始化，至少有一位for ( i = k - 1; i 0; i- ) /逐个考查其前面的数，寻找以前面的某位为倒数第二位的最优方案if ( ai ak & bi = max ) /如果第k位比第i位小，并且以它为倒数第二位更优，则更新max = bi + 1;bk = max; /存取以第k位为未位的最长下降序列的最优方案k+;cal ( k ); /继续考虑下一位int getmax () /获取最长的下降序列的元素个数为最最优方案int i, max = b1;for ( i = 1; i max )max = bi+1;return max;int min_system () /计算至少用几套系统int i, j, system30, current = 1;system1 = a1; /初始化为至少用一套，这套系统以后只能打高度为a1以下的啦 _for ( i = 2; i = totalN; i+ ) /逐个考查后面的导弹for ( j = 1; j = current; j+ ) /用已经启用的系统打第i颗导弹if ( ai current ) /如果已启用的系统都不能把它打下，只能启用一套新的啦:(system+current = ai; /该套系统的至高点为aireturn current; /返回共用了几套系统int main()int maxlength, MinS;init ();cal (2);maxlength = getmax ();MinS = min_system ();printf ( %d %dn, maxlength, MinS );return 0;tj1048Tom的烦恼ProblemTom是一个非常有创业精神的人，由于大学学的是汽车制造专业，所以毕业后他用有限的资金开了一家汽车零件加工厂，专门为汽车制造商制造零件。由于资金有限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他加工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的，但开始和结束时间相同不算冲突）。 Tom当然希望能把所有的零件都加工完，以得到更多的加工费，但当一些零件的加工时间要求有冲突时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得尽量多的加工费，Tom不知如何进行取舍。现在请你帮Tom设计一个程序，合理选择部分（或全部）零件进行加工，使得得到最大的加工费。 Input第一行是一个整数m,表示测试数据的个数。 每组测试数据的第一行是一个整数n(n=30000)，表示共有n个零件须加工。 接下来的n行中，每行有3个整数，分别表示每个零件加工的时间要求。 第一个表示开始时间，第二个表示该零件加工的结束时间，第三个表示加工该零件可以得到的加工费。 注：数据中的每个数值不会超过100000. Output对每组测试数据,输出一个整数，表示Tom可以得到的最大加工费。 Sample Input131 3 104 6 202 5 25Sample Output30解题思路：动态规划best为个结束时间的最大效益，并对输入的数据按照结束时间排序#includelong int t,n,a300003,best100000,bestw; /* bestw为划分阶段的最优，与besti比较选择最优的*/void qsort(int l,int r);int partion(int l,int r);int main()long int i,j,num=1,max;scanf(%ld,&t);while(num+=t)max=0;scanf(%ld,&n);for(i=0;in;i+)scanf(%ld%ld%ld,&ai0,&ai1,&ai2);qsort(0,n); /*对a按照结束时间排序*/max=an-11; /*找出结束时间最晚者，即为a排好序之后的最后面的元素*/best0=0;for(i=1,j=0;i=max;i+)besti=besti-1;for(;jn&aj1=i;j+)bestw=bestaj0+aj2;if(bestibestw) /*选择最优策略*/besti=bestw;printf(%ldn,bestmax);return(0);void qsort(int l,int r)int q;if(lr)q=partion(l,r);qsort(l,q);qsort(q+1,r);int partion(int l,int r)int i,j,temp,k;temp=al1;i=l+1;j=r-1;while(1)while(ai1temp&i=temp&jl)j-;if(i=j)break;k=ai1;ai1=aj1;aj1=k;k=ai0;ai0=aj0;aj0=k;k=ai2;ai2=aj2;aj2=k;al1=aj1;aj1=temp;temp=al0;al0=aj0;aj0=temp;temp=al2;al2=aj2;aj2=temp;return(j);tj1049砝码问题Problem有一组砝码，重量互不相等，分别为m1、m2、m3mn；它们可取的最大数量分别为x1、x2、x3xn。 现要用这些砝码去称物体的重量,问能称出多少种不同的重量。 Input第一行为一整数t,表示有t组测试数据。 每组测试数据第一行一个整数n（n=10），表示有多种不同的砝码； 第二行n个整数（中间用空格分隔），m1、m2、m3mn，分别表示n个砝码的重量；（1=mi=20） 第三行n个整数（中间用空格分隔），x1、x2、x3xn，分别表示n个砝码可取的最大数量。（1=xi=20） Output每组数据输出仅一行，一个整数，表示利用给定的砝码可以称出的不同的重量数。 注：包括0。 Sample Input121 22 1Sample Output5/*动态规划*/#includeint a112;char b114001,c4001; /*bi,j表示前i个砝码是否能够称出j重量，c中元素意义相同，为了方便计数*/int main()int i,j,k,t,n,num=1,max,m,sum;scanf(%d,&t);while(num+=t)max=0;sum=0;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai0);for(i=1;i=n;i+)scanf(%d,&ai1);max=max+ai1*ai0;for(i=0;i=max;i+)b0i=0;ci=0;for(i=0;i=n;i+)bi0=1;for(i=1;i=n;i+)for(j=1;j=max;j+)bij=0;c0=1;for(i=1;i=n;i+) for(j=1;j=max;j+)for(k=0;k=ai1;k+) m=j-ai0*k;if(m0) /此时意味着以后的重量都不能实现了break;if(bi-1m) /能够称出该重量，并置为1bij=1;cj=1;break;for(i=0;i=max;i+)if(ci)sum+;printf(%dn,sum);return(0);tj1050单词的划分Problem有一个很长的由小写字母组成字符串。为了便于对这个字符串进行分析，需要将它划分成若干个部分，每个部分称为一个单词。 出于减少分析量的目的，我们希望划分出的单词数越少越好。你就是来完成这一划分工作的。 Input第一行为一整数T，表示有T组测试数据。 每组测试数据第一行为一字符串。(长度小于256) 第二行为一整数N。（1=N=100） 以下N行，每行一个单词。 Output一个整数，表示字符串可以被划分成的最少的单词数。 Sample Input1realityour5realrealityityourourSample Output2/*典型的动态规划*/#include#include#define maxint 32767 /*初始化不能构成单词的情况*/char a100256,b256,c256; /*a数组做单词输入，c用来取b中的字符段*/int d256; /*选择最优方案*/int main()int num=1,i,j,k,t,n,m,l;scanf(%d,&t);while(num=t)scanf(%s,b);l=strlen(b);scanf(%d,&n);for(i=0;in;i+)scanf(%s,ai);d0=0;for(i=0;il;i+)di=maxint;for(k=0;k=i;k+)ck=bk;ck=0;for(k=0;kn;k+)if(strcmp(c,ak)=0)di=1;break;for(j=1;j=i;j+)m=0;for(k=j;k=i;k+)cm+=bk;cm=0;for(k=0;kn;k+)if(strcmp(c,ak)=0) /从j位置到i位置是一个单词if(dj-1+1di) /选择最优策略di=dj-1+1;break;printf(%dn,dl-1);num+;return(0);1147 战略游戏-版本2Time Limit:1s Memory Limit:1000kProblemBob喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速玩过游戏的办法。现在他有个问题。 他要建立一个古城堡，城堡中的路形成一棵树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能了望到所有的结点(和tju1041就差这一个词哦)。 注意，某个士兵在一个结点上时，与该结点相连的所有结点将都可以被了望到。 请你编一程序，给定一树，帮Bob计算出他需要放置最少的士兵。 Input第一行为一整数，表示有组测试数据 每组测试数据表示一棵树，描述如下： 第一行 N，表示树中结点的数目。 第二行至第N+1行，每行描述每个结点信息，依次为：该结点标号i，k(后面有k条边与结点I相连)。 接下来k个数，分别是每条边的另一个结点标号r1，r2，.，rk。 对于一个n(0 n = 1500)个结点的树，结点标号在0到n-1之间，在输入数据中每条边只出现一次。 Output输出文件仅包含一个数，为所求的最少的士兵数目。 例如，对于如下图所示的树： 答案为1（只要一个士兵在结点1上）。 Sample Input240 1 11 2 2 32 03 053 3 1 4 21 1 02 00 04 0Sample Output12解题思路：贪心法，总是取当前可以照顾最多未安排哨兵的结点放上哨兵，直到所有的结点都能被看到源代码：#include #include /找出控制价值（即父结点+子结点+本身）最大的结点,放上哨兵，然后更新/每个结点的控制价值，直到所有结点都考查typedef struct child /子结点结构int no;struct child *next; Child, *CList;typedef struct parent /父结点结构int no;struct child *firstc;struct parent *next; Parent, *PList;int *sel, *parentN, *value, n;PList phead;int getdata() /获取输入信息并建立树int m, i, j, is_p_head=1, is_c_head=1, c_no, p_no;PList p, q;CList w, v;scanf ( %d, &n );if ( n = 0 )return 0;sel = ( int * ) malloc ( sizeof ( int ) * ( n + 1 ) );parentN = ( int * ) malloc ( sizeof ( int ) * n );value = ( int * ) malloc ( sizeof ( int ) * n );for ( i = 0; i n; i+ )seli = parentNi = valuei = 0;parentN0 = n;seln = 1;for ( i = 0; i n; i+ )seli = 0;for ( i = 0; i no = i;q-firstc = NULL;q-next = NULL; valuei = m + 2;if ( is_p_head )phead = p = q;is_p_head = 0;elsep-next = q;p = q;is_c_head = 1;for ( j = 0; j no = c_no;v-next = NULL;parentNc_no = i;if ( is_c_head )p-firstc = w = v;is_c_head = 0;elsew-next = v;w = v;value0-;return 1;PList selMax() /选择最大控制价值的结点，并返回其指针int i;PList p = NULL, q = NULL;int max = 0;for ( i = 0; i next )if ( valuei = max )q = p;max = valuei;return q;void renew ( PList p ) /更新各结点的控制价值CList w;PList h;int i;selp-no = 1;selparentNp-no = 1;for (w = p-firstc; w != NULL; w = w-next )selw-no = 1;for ( i = 0, h = phead; i next )if ( valuei != 0 )valuei = !selparentNi + !seli;for ( w = h-firstc; w != NULL; w = w-next )valuei = valuei + !selw-no;int cal() /计算int count=0;PList p;getdata ();if ( n = 0)return 0;while ( ( p = selMax () ) != NULL )renew ( p );count+;return count;int main() /主函数int t,i;scanf(%d,&t);for( i = 1; i = t; i+ )printf ( %dn, cal () );return 0;1169 Paint 广告印刷Time Limit:3s Memory Limit:32768kProblem最近，afy决定给TOJ印刷广告，广告牌是刷在城市的建筑物上的，城市里有紧靠着的N个建筑。afy决定在上面找一块尽可能大的矩形放置广告牌。我们假设每个建筑物都有一个高度，从左到右给出每个建筑物的高度H1,H2HN，且0Hi=1,000,000,000，并且我们假设每个建筑物的宽度均为1。Input输入由多组数据组成，每组数据第一行是N，且N = 1,000,000。接下来N行每行一个数字，依次为Hi。 Output对于每组数据，输出一行，表示广告牌的最大面积。 Sample Input53060504555Sample Output180解题思路：动态规划如注释源代码：#include #include int main ()long i, n;long *l, *r, *h;/当前位置i向左右两边扩展(扩展至比它更低的楼或者边界为止）long long max; /如果不能编译通过，可换成_int64，相应的scanf(%I64d,&max)while ( scanf ( %ld, &n ) != EOF )h = ( long * ) malloc ( sizeof ( long ) * ( n + 2 ) ); /开辟内存空间 l = ( long * ) malloc ( sizeof ( long ) * ( n + 2 ) );r = ( long * ) malloc ( sizeof ( long ) * ( n + 2 ) );for ( i = 1; i = n; i+ ) /输入数据scanf ( %ld, &hi );max = 0; /最优初始为0h0 = hn+1 = 0;/两边界初始为0，以防止扩展出界for ( i = 1; i = n; i+ ) /向左边扩展，可借助其左边的结果快速扩展for ( li = i; hi = 1; i- ) /向右边扩展，可借助其右边的结果快速扩展for ( ri = i; hi = hri+1; ri = rri+1 );for ( i = 1; i max )max = ( long long ) ( ri - li + 1 ) * hi;printf ( %lldn, max );free ( h );free ( l );free ( r );return 0;1059 数的计数Time Limit:1s Memory Limit:50000kProblem先输入一个自然数n(n3000000)，然后对此自然数按照如下方法进行处理 1、不作任何处理: 2、在它的左边加上一个自然数，但该自然数不能超过原数的一半; 3、加上数后，继续按此规则进行处理，直到不能再而 自然数为止。 例如n=66162612636136所以满足要求的个数为6。 Input包含多个测试数据,每行是一个整数n(1=n=3000000) Output一个整数,表示解的个数(保证不超过50位) Sample Input6Sample Output6解题思路：动态规划源代码：#include #define Max 1500003int aMax6 = 0 ;int current;void add ( int *sum, int *add1, int *add2 )/相加并把和存入sum数组中，每个int型可存九位十进制数字int i;int flg = 0;for ( i = 0; i current; i+ )sumi = add1i + add2i + flg;flg = sumi / 1000000000;sumi = sumi % 1000000000;if ( flg )sumi = flg;current+;void init ()/递推 ai = ai-1 + a(i+1)/2int i;a00 = 0;a10 = 1;a20 = 2;a30 = 4;current = 1;for ( i = 4; i = 0; i- )if ( aki != 0 )break;printf ( %d, aki );for ( j = i - 1; j = 0; j- )length = 0;temp = akj;dotemp = temp / 10;length+;while ( temp != 0 ); for ( r = 8; r = length; r-)/每位int型存九位数字，如非首位，则其前导0也要输出printf(0);printf ( %d, akj );printf ( n );return 0;1086 字符串的距离Time Limit:2s Memory Limit:20000kProblem设有字符串X，我们称在X的头尾及中间插入任意多个空格后构成的新字符串为X的扩展串，如字符串X为“abcbcd”，则字符串“abcbcd”，“abcbcd”和“abcbcd”都是X的扩展串，这里“”代表空格字符。 如果A1是字符串A的扩展串，B1是字符串B的扩展串，A1与B1具有相同的长度，那么我们定义字符串A1与B1的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的ASCII码的差的绝对值，而空格字符与其它任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为O。在字符串A、B的所有扩展串中，必定存在两个等长的扩展串A1、B1，使得A1与B1之间的距离达到最小，我们将这一距离定义为字符串A、B的距离。 请你写一个程序，求出字符串A、B的距离。 Input有多组数据,每一组数据第一行为字符串A，第二行为字符串B，A、B均由小写字母组成且长度均不超过2000，第三行为一个整数K，1K100，表示空格与其它字符的距离。 Output每组数据一行包含一个整数，表示要求的字符串A、B的距离。 Sample Inputcmcsnmn2Sample Output10解题思路：动态规划具体如下面代码源代码：#include #include #include using namespace std;#define Max 2001char s1Max, s2Max;int fMaxMax;int min (int a, int b, int c) /返回三者中的最小者int x = a;if (x b)x = b;if (x c) x = c;return x;int dis (int i, int j) /返回s1的第i个字母与s2的第j个字母的距离int d = abs(s2j-1 - s1i-1);return d;int main ()int l1, l2, i, j, k;while (scanf(%s, s1) = 1) scanf(%s, s2);scanf(%d, &k);l1 = strlen(s1);l2 = strlen(s2);for (i=0; i=l1; i+)fi0 = i * k;for (i=0; i=l2; i+)f0i = i * k;for (i=1; i=l1; i+) /DPfor(j=1; j=l2; j+)/在三种情况取最优的fij = min(fi-1j + k, fij-1 + k, fi-1j-1 + dis(i, j);printf (%dn, fl1l2);return 0;1087 垃圾陷阱Time Limit:1s Memory Limit:32768kProblem卡门农夫约翰极其珍视的一条Holsteins奶牛已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D (2 = D = 100)英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间t(0 t = 1000)，以及每个垃圾堆放的高度h(1 = h = 25)和吃进该垃圾能维持生命的时间f(1 = f = 30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。 Input本题有多组测试数据. 第一行为2个整数，D 和 G (1 = G = 100)，G为被投入井的垃圾的数量。第二到第G+1行每行包括3个整数：T (0 T = 1000)，表示垃圾被投进井中的时间；F (1 = F = 30)，表示该垃圾能维持卡门生命的时间；和 H (1 = H = 25)，该垃圾能垫高的高度。 Output如果卡门可以爬出陷阱，输出一个整表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。 Sample Input20 45 4 99 3 212 6 1013 1 1Sample Output13解题思路：动态规划源代码：#include typedef struct int t;int f;int h;St;St r102, p;int main ()int i, j, k, g, d, m, ans, max;int l1021