首页 > 专题系列 > Java解POJ > POJ 1836 Alignment [解题报告] Java
2013
11-10

POJ 1836 Alignment [解题报告] Java

Alignment

问题描述 :

In the army, a platoon is composed by n soldiers. During the morning inspection, the soldiers are aligned in a straight line in front of the captain. The captain is not satisfied with the way his soldiers are aligned; it is true that the soldiers are aligned in order by their code number: 1 , 2 , 3 , . . . , n , but they are not aligned by their height. The captain asks some soldiers to get out of the line, as the soldiers that remain in the line, without changing their places, but getting closer, to form a new line, where each soldier can see by looking lengthwise the line at least one of the line’s extremity (left or right). A soldier see an extremity if there isn’t any soldiers with a higher or equal height than his height between him and that extremity.

Write a program that, knowing the height of each soldier, determines the minimum number of soldiers which have to get out of line.

输入:

On the first line of the input is written the number of the soldiers n. On the second line is written a series of n floating numbers with at most 5 digits precision and separated by a space character. The k-th number from this line represents the height of the soldier who has the code k (1 <= k <= n).

There are some restrictions:

• 2 <= n <= 1000

• the height are floating numbers from the interval [0.5, 2.5]

输出:

The only line of output will contain the number of the soldiers who have to get out of the line.

样例输入:

8
1.86 1.86 1.30621 2 1.4 1 1.97 2.2

样例输出:

4

解题代码:

//* @author: 
import java.util.Scanner;
public class Main{
   private int n;
   private double a[];
   int b[],c[],sum[];
   
   public Main(int n,double a[]){
    this.n=n;
    this.a=a;
    b=new int[n+1];
    c=new int[n+1];
    sum=new int[n+1];
  }

   public static void main(String args[]){
     Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      double a[]=new double[n+1];
      for(int i=1;i<=n;i++){
        a[i]=sc.nextDouble();//下标从1开始
   
       }
      Main ma=new Main(n,a);
     // ma.showB();
      //ma.showC();
      System.out.println(ma.doIt());
      
  }

   private void showB(){
     for(int i=1;i<=n;i++){
        System.out.println(b[i]+"  ");
     }
    }

   private void showC(){
     for(int i=1;i<=n;i++){
        System.out.println(c[i]+"  ");
     }
   }
  
   private void lis(){//a[]的前i个元素中,最长递增子序列的长度为b[i]
    b[1] = 1;
    for (int i=2;i<=n;i++)
    {
        int max = 0;
        for (int j=1;j< i;j++)
        {
            if (a[j]< a[i] && b[j]>max)
            {
                 max = b[j];
            }
        }
        b[i] = max + 1;
    } 
  // showB();
}

private void flis()//a[]的从后向前的n-i+1元素中,最长递增子序列的长度为c[i]
{
     c[n] = 1;
    for (int i=n-1;i>=1;i--)
    {
        int max = 0;
        
        for (int j=n;j>i;j--)
        {
            if (a[j]< a[i] && c[j]>max)
            {
                max = c[j];
            }
        }
        c[i] = max + 1;
    }
}

 

  private int doIt(){
    lis();
    flis();
    int min=n;
   for(int i=1;i<=n;i++){
      for (int j = i + 1; j <= n; j++) {//最高点可以有两个,如果a[i]后面有与自己等高的人
            if (a[i] == a[j]){
              if(c[i]<=c[j])
                c[i]=c[j]+1;
            }
        }

      sum[i]=n-(b[i]+c[i]-1);
      if(sum[i]< min){
           min=sum[i];
      }
   }
  return min;
 }

}

  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”