首页 > 专题系列 > Java解POJ > POJ 1974 The Happy Worm [解题报告] Java
2013
11-10

POJ 1974 The Happy Worm [解题报告] Java

The Happy Worm

问题描述 :

The Happy Worm lives in an m*n rectangular field. There are k stones placed in certain locations of the field. (Each square of the field is either empty, or contains a stone.) Whenever the worm sleeps, it lies either horizontally or vertically, and stretches so that its length increases as much as possible. The worm will not go in a square with a stone or out of the field. The happy worm can not be shorter than 2 squares.

The question you are to answer is how many different positions this worm could be in while sleeping.

输入:

The first line of the input contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The first line of each test case contains three integers m, n, and k (1 <= m,n,k <= 131072). The input for this test case will be followed by k lines. Each line contains two integers which specify the row and column of a stone. No stone will be given twice.

输出:

There should be one line per test case containing the number of positions the happy worm can be in.

样例输入:

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

样例输出:

9

解题代码:

import java.util.ArrayList;  
    import java.util.List;  
    import java.util.Scanner;  
      
    public class Main{  
      
        public static final int MAX = 152;  
        static List< Integer> v[];  
        static int dp[][];  
        static int p;  
        static int root;  
          
        public static void main(String[] args) {  
              
            Scanner scan = new Scanner(System.in);  
              
            int n = scan.nextInt();  
            p = scan.nextInt();  
              
            boolean s[] = new boolean[n+1];  
            v = new ArrayList[n+1];  
            java.util.Arrays.fill(s, true);  
            dp = new int[n+1][p+1];  
              
            for(int i=0;i<=n;i++)  
                java.util.Arrays.fill(dp[i], MAX);  
              
            for(int i=1;i<=n;i++)  
                v[i] = new ArrayList< Integer>();  
              
            for(int i=1;i< n;i++){  
                int u = scan.nextInt();  
                int t = scan.nextInt();  
                v[u].add(t);  
                s[t] = false;  
            }  
              
            for(int i=1;i<=n;i++){  
                if(s[i]){  
                    root = i;  
                    dfs(root);  
                    break;  
                }  
            }  
              
            int ans = MAX;  
            for(int i=1;i<=n;i++)  
                ans = Math.min(ans,dp[i][p]);  
              
            System.out.println(ans);  
      
        }  
      
        public static void dfs(int u) {  
              
            for(int i=0;i< v[u].size();i++){  
                  
                dfs(v[u].get(i));  
                  
            }  
              
            if(u == root)  
                dp[u][1] = v[u].size();  
            else  
                dp[u][1] = v[u].size()+1;  
              
         for(int i=0;i< v[u].size();i++){  
            for(int j=p-1;j>=1;j--){  
               if(dp[u][j]< MAX){  
                 for(int k=1;k+j<=p;k++){  
                   if(dp[u][k]< MAX){  
                      dp[u][j+k] = Math.min(dp[u][j+k], dp[u][j]+dp[v[u].get(i)][k]-2);//每次加一个子树 更新d[u][2..P]  
                            }  
                        }  
                    }  
                }  
            }  
              
        }  
      
    }

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  3. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。