[白俊]#2352半導体設計

9432 ワード
白駿 algorithm LIS テキストリンク

質問する


半導体を設計する場合、n個のポートを他のn個のポートに接続する必要がある場合がある.

たとえば、左の図は、n個のポートと他のn個のポートを接続する方法を示しています.ただし、このように接続すると、接続線は互いに絡み合っているので、このように接続することはできません.n個のポートが他のn個のポートにどのように接続されるべきかを指定する場合は、ベースラインの交差(オーバーラップ)を回避しながら、最大何個のポートに接続できるかを決定するプログラムを作成します.

入力


第1行は整数n(1≦n≦40000)を与える.次の行では、1番ポートに順次接続するポート番号、2番ポートに接続するポート番号、…、n番ポートに接続するポート番号を示します.これらの数が1以上n以下であると仮定し,等しくならない.

しゅつりょく


最初の行に最大接続数を出力します.

入力例1

6
4 2 6 3 1 5

サンプル出力1

3

に答える


この問題はLIS(最長増分部分数列)アルゴリズムで解くことができる.動的プログラミングを用いてLISを実現した.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int dp[] = new int[N];
        int res = 0;

        String[] input = br.readLine().split(" ");
        for(int i=0; i<N; i++)
            arr[i] = Integer.parseInt(input[i]);

        for(int i=1; i<N; i++) {
            for(int j=i-1; j>=0; j--) {
                if(arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        for(int i=0; i<N; i++)
            res = Math.max(res, dp[i]);

        System.out.println(res+1);
    }
}
依存注入01)DI概念
Lifecycle