結果

問題 No.393 2本の竹
コンテスト
ユーザー htensai
提出日時 2020-01-24 09:40:09
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 1,820 bytes
コンパイル時間 3,531 ms
コンパイル使用メモリ 79,016 KB
実行使用メモリ 217,628 KB
最終ジャッジ日時 2024-09-13 20:14:59
合計ジャッジ時間 7,417 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.*;

public class Main {
    public static void main(String[]  args) {
        Scanner sc = new Scanner(System.in);
        int d = sc.nextInt();
        for (int i = 0; i < d; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            int m = sc.nextInt();
            int[] arr = new int[m];
            HashMap<Bamboo, Integer>[] dp = new HashMap[m];
            for (int j = 0; j < m; j++) {
                arr[j] = sc.nextInt();
                dp[j] = new HashMap<Bamboo, Integer>();
            }
            System.out.println(dfw(m - 1, new Bamboo(n1, n2), arr, dp));
        }
    }
    
    static int dfw(int idx, Bamboo bamboo, int[] arr, HashMap<Bamboo, Integer>[] dp) {
        if (bamboo.n1 < 0) {
            return Integer.MIN_VALUE;
        }
        if (idx < 0) {
            return 0;
        }
        if (dp[idx].containsKey(bamboo)) {
            return dp[idx].get(bamboo);
        }
        int ans = Math.max(dfw(idx - 1, bamboo, arr, dp), Math.max(dfw(idx - 1, bamboo.useFirst(arr[idx]), arr, dp), dfw(idx - 1, bamboo.useLast(arr[idx]), arr, dp)) + 1);
        dp[idx].put(bamboo, ans);
        return ans;
    }
    
    static class Bamboo {
        int n1;
        int n2;
        
        public Bamboo(int n1, int n2) {
            this.n1 = Math.min(n1, n2);
            this.n2 = Math.max(n1, n2);
        }
        
        public int hashCode() {
            return n1 + n2;
        }
        
        public boolean equals(Object o) {
            Bamboo b = (Bamboo)o;
            return n1 == b.n1 && n2 == b.n2;
        }
        
        public Bamboo useFirst(int x) {
            return new Bamboo(n1 - x, n2);
        }
        
        public Bamboo useLast(int x) {
            return new Bamboo(n1, n2 - x);
        }
    }
}
0