资源描述
A Free sample background from,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Slide,9,作业中的两道题,1398 square,和,2281 ,wordstack,1398 -,square,Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?,The first line of input contains N, the number of test cases. Each test case begins with an integer 4 M 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.,因为,M,最大为,20,，所以，如果用,DFS,还是可以接受的。,1398 -,square,由所有火柴棒的长度和，我们可以求出要组成正方形的边长。我们设边长为,length,。,在搜索前，首先可以把边长为分数的，也就是火柴棒的长度和不能被,4,整除的，排除掉。,其实问题可以转化为从,M,个数中挑出,4,组和为,length,的数。,首先、从,M,个数中搜索出和为,lenth,的数。如果能搜到，则接着从剩余的数中，进行同样的搜索，依此类推，一共进行,4,段这样的搜索。,如果某一段搜索失败，则回溯到上一段搜索。,如果一直回溯到第一段的搜索，仍未能找到解，则说明无解。,1398 -,square,具体的搜索过程：,将长度按从大到小排序。,对应正方形的,4,条边，进行,4,段同样的搜索。而且这,4,段搜索也是递归式的，就是说，当第一段边搜索到后，便递归进行下一段的搜索。由此可见，搜索过程中要用到的信息包括：,1,、当前是第几段。,2,、当前段还剩余的长度。,3,、搜索的起始位置。,每段搜索的过程是相同的：,因为到最后，所有的火柴棒都是会被用到的，所以，每当开始一个新段的搜索时，总是把剩余的第一个数放入，在这段的搜索过程中，它始终是放入状态。然后进入堆栈的下一层，试着放入下一个剩余的数，如果放入这个数后递归到下面未回溯回来，则说明已经找到最后答案，程序结束。如果得到回溯，那么把该数取出，同理再试着放入排在它后面的数。,为什么需要搜索的起始位置？,1398 -,square,搜索的起始位置很重要，它关系到每层递归可选的状态数，和程序运行时间紧密相连。,起始位置就是，在每次进入递归函数的时候，应该从哪个位置的数开始试着放入，前面说到，如果这次递归要放入的是一个段的第一个数，这个数肯定是剩余的第一个数，而且这个数是不会被取出的，也就是说，这一层的可选状态只有一个，如果放入这个数之后，后面发现无法搜索到一个完整的边，那么说明剩余的数到达最终的目标，必须回溯到上一个段。,如果这次递归要放入不是一个段的第一个数，那么它的起始位置肯定是在它上一层递归放入的数的后面，但是它前面可能还存在没有被放入的数，这些数就不用再试了吗？,因为是对同一个段的搜索，所以，组成这个段的数被放入的顺序是没有关系的。所以，如果一个数作为一个段的第一个数放入不合适，那么它作为第二个数或第三个数放入肯定也是不合适的。,1398 -,square,根据前面所分析，我们可以得出递归函数应该包括三个参数：,当前是第几段。,当前段还剩余的长度。,搜索的起始位置。,int,dfs(int,duan,int,start,int,left),.,int,dfs(int,duan,int,start,int,left),if(left,= 0),/,如果,left,为,0,，开始新的一段,if(duan,= 3) return 1;,/,如果当前段为,3,，则程序结束,for(start,= 0;,instart, ,/,找到剩余数中第一个为放入数,instart, = 1;,/,找到后标记放入,if(dfs(,duan,+ 1,start + 1,length -,numstart,),return 1;,/,开始该段的递归搜索,instart, = 0;,/,如果未找到，则反标记，,return 0;,/,回溯到上一段,int,i;,if(start,= n) return 0;,/,没有可搜索数，返回,for(i,= start; i left),/,i,已放入或无法放入,continue;,if(i, 0 & !,ini,- 1 &,numi, =,numi,- 1),continue;,/,剪枝操作,ini, = 1;,if(dfs(,duan,i + 1,left -,numi,) return 1;,ini, = 0;,return 0;,2281 -,wordstack,Given a collection of N words, find an arrangement of the words that divides them among N lines, padding them with leading spaces to maximize the number of non-space characters that are the same as the character immediately above them on the preceding line. Your score for this game is that number.,数据范围：,1=N max) max = t;,/,比较更新,return;,for(i,= 0; i n; i+),if(!marki,),marki, +;,/,标记,i,strlevel, = i;,/,保存,i,到序列中,DFS(level,+ 1);,/,递归到第,level+1,层,marki, -;,/,反标记,i,
展开阅读全文