結果
問題 |
No.390 最長の数列
|
ユーザー |
![]() |
提出日時 | 2016-12-01 15:31:09 |
言語 | Java (openjdk 23) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,561 bytes |
コンパイル時間 | 2,348 ms |
コンパイル使用メモリ | 79,020 KB |
実行使用メモリ | 136,280 KB |
最終ジャッジ日時 | 2024-11-27 15:48:17 |
合計ジャッジ時間 | 46,129 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 6 WA * 2 TLE * 7 |
ソースコード
import java.util.*; import java.lang.*; import java.io.*; class Main{ public static void main (String[] args) throws java.lang.Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); String[] lines = br.readLine().toString().split(" "); ArrayList<Integer> list = new ArrayList<Integer>(); for(String st:lines){ list.add(Integer.parseInt(st)); } Collections.sort(list); HashMap<Integer,ArrayList<Integer>> map = new HashMap<Integer,ArrayList<Integer>>(); for(int i=0;i<list.size();i++){ ArrayList<Integer> next = new ArrayList<Integer>(); map.put(i,next); int now = list.get(i); for(int j=i+1;j<list.size();j++){ if(list.get(j)%now == 0){ next.add(j); } } } int ans = calc(map,0,n); System.out.println(ans); } static HashMap<Integer,Integer> ans_map = new HashMap<Integer,Integer>(); public static int calc(HashMap<Integer,ArrayList<Integer>> map,int idx,int n){ if(ans_map.containsKey(idx)){ return ans_map.get(idx); } int max = 1; for(int i=idx;i<n;i++){ ArrayList<Integer> next = map.get(i); for(int j:next){ max = Math.max(max,calc(map,j,n)+1); } } ans_map.put(idx,max); return max; } }