首页 > ACM题库 > HDU-杭电 > hdu 2198 How many elements you must throw out?[解题报告]Java
2013
12-30

hdu 2198 How many elements you must throw out?[解题报告]Java

How many elements you must throw out?

问题描述 :

You have a sequence of numbers from which you must create the longest subsequence satisfying the following condition: it can be ‘cut’ into two parts that share exactly one common element (the last element of the first part is the first element of the second part), and the first part is sorted in strictly ascending order while the second part is sorted in strictly descending order. For example, the sequence { 1, 4, 6, 5, 2, 1 } can be ‘cut’ into { 1, 4, 6 } and { 6, 5, 2, 1 }. The two parts share the 6(see the following graph), and the first sequence is sorted in ascending order while the second sequence is sorted in descending order.

You are given a sequence of numbers. Output the minimal number of elements you must throw out from the given sequence such that the remaining subsequence satisfies the condition described above.

输入:

There are multiple test cases. At first line of each case, there’s an integer N (1<=N<=50) and N integers followed at second line representing the subsequence, each of which ranges from 1 to 1000000000.Input ends when N is 0.

输出:

There are multiple test cases. At first line of each case, there’s an integer N (1<=N<=50) and N integers followed at second line representing the subsequence, each of which ranges from 1 to 1000000000.Input ends when N is 0.

样例输入:

6
1 4 6 5 2 1
5
2 2 2 2 2
0

样例输出:

0
4

import java.util.Scanner;
/**
 * @copyright www.acmerblog.com
 * @author coder
 *
 */
public class Hdu2198 {

	
	public static void findMinimumCuts(int arr[])
	{
		
		int size = arr.length;
		int lis[] = new int[size];
		int lds[] = new int[size];
		// Longest Increasing sequence
		   for(int i = 0; i < size; ++i)
		   {
		       for(int j = 0; j < i; ++j)
		       {
		           if(arr[j] < arr[i])
		           {
		               lis[i] = Math.max(lis[j] + 1, lis[i]);
		           }
		       }
		   }
		   
		   // Longest decreasing sequence
		   for(int i = size - 1; i >= 0; --i)
		   {
		      for(int j = size - 1; j > i; --j)
		      {
		          if(arr[j] < arr[i])
		          {
		             lds[i] = Math.max(lds[j] + 1, lds[i]);
		          }
		      }
		   }
		   
		   int best = 0;
		   for(int i = 0; i < size; ++i)
		   {
		      best = Math.max(best, lds[i] + lis[i]);
		   }
		  // System.out.println("Best"+best);
		   //System.out.println("Number to be removed : " + (size - best - 1));
		System.out.println(size - best - 1);
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n;
		while(true){
			n = scan.nextInt();
			if(n == 0) break;
			int a[] = new int[n];
			for(int i=0; i<n; i++) a[i] = scan.nextInt();
			findMinimumCuts(a);
		}
//		int a[] = {1, 2, 1, 2, 3, 2, 1, 2, 1};
//		int b[] = {4,5,65,34,786,45678,987,543,2,6,98,580,4326,754,54,2,1,3,5,6,8,765,43,3,54};
//		findMinimumCuts(a);
//		findMinimumCuts(b);
	}

}

 


  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。