2597 Line Segment Erase

「2597 Line Segment Erase」の編集履歴（バックアップ）一覧はこちら

「2597 Line Segment Erase」(2006/04/17 (月) 02:21:47) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**2597 Line Segment Erase
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2597
**解答例
 import java.util.*;
 
 public class Main{
     static int[][][] mem;
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(sc.hasNext()){
             int n = sc.nextInt();
             LineSegment ls[] = new LineSegment[n+1];
             ls[0] = new LineSegment(-30000,-20000);
             for(int i=1;i<=n;i++){
                 ls[i] = new LineSegment(sc.nextInt(),sc.nextInt());
             }
             Arrays.sort(ls);
             
             int m = sizeOfMaxStableSet(ls);
             int e = n+1 - m;
             mem = new int[m][n+1][n+1];
             for(int i=0;i<m;i++){
                 for(int j=0;j<=n;j++){
                     Arrays.fill(mem[i][j],-1);
                 }
             }
             int c = numOfMaxStableSet(ls,m-1,1,0);
             System.out.println(e+" "+c);
         }
     }
     private static int numOfMaxStableSet(LineSegment[] ls,int size,int k,int l){
         if(k>=ls.length) return 0;
         if(mem[size-1][k][l]==-1){
             int ret;
             
             if(ls.length-k<size){
                 ret = 0;
             }
             else if(ls[k].x0<ls[l].x1){
                 ret = numOfMaxStableSet(ls,size,k+1,l);
             }
             else if(size==1){
                 ret = 1 + numOfMaxStableSet(ls,size,k+1,l);
             }
             else{
                 ret = numOfMaxStableSet(ls,size-1,k+1,k) + numOfMaxStableSet(ls,size,k+1,l);
             }
             
             mem[size-1][k][l] = ret;
             return ret;
         }
         else{
             return mem[size-1][k][l];
         }
     }
     private static int sizeOfMaxStableSet(LineSegment[] ls){
         int ret = 0;
         int x = Integer.MIN_VALUE;
         for(int i=0;i<ls.length;i++){
             if(x<=ls[i].x0){
                 x = ls[i].x1;
                 ret++;
             }
         }
         return ret;
     }
 }
 
 class LineSegment implements Comparable<LineSegment>{
     int x0;
     int x1;
     LineSegment(int x0, int x1) {
         this.x0 = Math.min(x0,x1);
         this.x1 = Math.max(x0,x1);
         if(this.x0==this.x1){
             throw new RuntimeException();
         }
     }
     public boolean equals(Object o){
         LineSegment ls = (LineSegment)o;
         return this.x0==ls.x0&&this.x1==ls.x1;
     }
     public int compareTo(LineSegment ls){
         if(this.x1!=ls.x1) return this.x1 - ls.x1;
         else return this.x0 - ls.x0;
     }
 }