首页 > 搜索 > DFS搜索 > POJ 1020 Anniversary Cake [解题报告] Java
2013
11-08

POJ 1020 Anniversary Cake [解题报告] Java

Anniversary Cake

问题描述 :

Nahid Khaleh decides to invite the kids of the “Shahr-e Ghashang” to her wedding anniversary. She wants to prepare a square-shaped chocolate cake with known size. She asks each invited person to determine the size of the piece of cake that he/she wants (which should also be square-shaped). She knows that Mr. Kavoosi would not bear any wasting of the cake. She wants to know whether she can make a square cake with that size that serves everybody exactly with the requested size, and without any waste.

输入:

The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by input data for each test case. Each test case consist of a single line containing an integer s, the side of the cake, followed by an integer n (1 ≤ n ≤ 16), the number of cake pieces, followed by n integers (in the range 1..10) specifying the side of each piece.

输出:

There should be one output line per test case containing one of the words KHOOOOB! or HUTUTU! depending on whether the cake can be cut into pieces of specified size without any waste or not.

样例输入:

2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1

样例输出:

KHOOOOB!
HUTUTU!

解题代码:

/* @author: */
import java.util.Scanner;
import java.util.Arrays;
public class Main{
 static int c[]=new int[11];//c[i]存放边长为i的小正方形的个数
 static int d[]=new int[41];//d[i]表示第i行填入小正方形后的最大横坐标
 static int s,n,sum;
 static boolean  ok;

public static void main(String args[])
{
    int t,it,i,tp;
    Scanner sc=new Scanner(System.in);
    t=sc.nextInt();//测试次娄
   
    for(it=1;it<=t;it++)//循环进行每一次测试
    {
        s=sc.nextInt();//“盘子”大正方形的边长
        n=sc.nextInt();//小正方形的个数
        Arrays.fill(c,0);//每次测试前清空
         ok=false;
        for(i=1;i<=40;i++) d[i]=1;//
        sum=0;
        for(i=1;i<=n;i++)//从命令行依次读入小正方形的边长
        {
            tp=sc.nextInt();
            c[tp]++;//边长为tp的小正方形的个数增加1
            sum+=tp*tp;//统计面积
        }
        if(sum!=s*s) ok=false;//如果所有小正方形面积之和不等于“盘子”面积
        else {ok=false;dfs(0);}//深度优先搜索
       
        if(ok) System.out.println("KHOOOOB!");
        else System.out.println("HUTUTU!");
    }
   }

  public static void dfs(int a)
{
    int i,j,put,p=0;
    boolean f;
    if(a==n) {//如果对所有的n个小正方形搜索完毕。
       ok=true;
       return;
    }

    //寻找未填的横坐标最小的点的纵坐标
    for(i=1,put=41;i<=s;i++){
        if(d[i]< put) {
          put=d[i];//put:横坐标
          p=i;//p:纵坐标
       }
    }

     //从横坐标最小的那列开始,从大到小搜索能填入的小正方形
    for(i=10;i>=1;i--)
        if(c[i]>0 && put+i-1<=s && p+i-1<=s)//在坐标(put,p)处能放得下小正方形c[i]
        {  
            for(j=p,f=true;j<=p+i-1;j++)
                if(d[j]>put) {f=false;break;}
            if(f)
            {
                for(j=p;j<=p+i-1;j++) d[j]+=i;//标记第i行填入小正方形后的最大横坐标
                
                c[i]--;
                dfs(a+1);
                c[i]++;//回朔
                for(j=p;j<=p+i-1;j++) d[j]-=i;
            }
        }
    }
}

  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  4. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.

  5. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。