結果

問題 No.45 回転寿司
ユーザー aimBULL
提出日時 2016-06-04 18:20:41
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,607 bytes
コンパイル時間 2,164 ms
コンパイル使用メモリ 88,040 KB
実行使用メモリ 111,544 KB
最終ジャッジ日時 2024-11-24 16:58:19
合計ジャッジ時間 178,245 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] sushi = new int[n];
		for(int i = 0; i < n && sc.hasNextInt(); i++){
			sushi[i] = sc.nextInt();
		}
		sc.close();

		int[] memo = Main.calc(n, sushi);

		Arrays.sort(memo);
		System.out.println(memo[memo.length - 1]);
	}

	// データの格納領域を作成する
	public static int[] create(int n){
		int[] memo = new int[(n + 1) / 2 + 1];
		memo[0] = 0;
		for(int i = 1; i < memo.length; i++){
			memo[i] = Integer.MIN_VALUE;
		}
		return memo;
	}

	// 最大の美味しさを計算する
	public static int[] calc(final int n, final int[] sushi){
		Deque<Node> stack	= new ArrayDeque<>();
		int[] memo = create(n);

		// 1つ目の寿司を選んだ状態を処理スタックに追加
		for(int i = 0; i < sushi.length; i++){
			Node startNode = new Node(i, i, 1, sushi[i]);
			stack.push(startNode);
		}

		// 寿司１つの場合の最大美味しさは事前に計算する
		int[] tmp = sushi.clone();
		Arrays.sort(tmp);
		memo[1] = tmp[tmp.length - 1];

		while(stack.size() > 0){
			Node current = stack.peek();

			// 存在しない寿司は削除して次へ
			if(current.pos >= sushi.length){
				stack.pop();
				continue;
			}

			// 存在しない寿司を取る場合は削除して次へ
			final int pos = current.nextPos;
			if(pos >= sushi.length){
				stack.pop();
				continue;
			}

			// 最大の美味しさを更新
			final int umami = current.totalUmami + sushi[pos];
			final int dishes = current.dishes + 1;
			if(umami >= memo[dishes]){
				memo[dishes] = umami;
			}

			// 次の寿司を選んだ状態を追加する
			stack.push(new Node(current.id, pos, dishes, umami));

			// 今回とは別の寿司を選ぶため更新をかける
			current.nextPos++;
		}

		return memo;
	}

}

class Sushi{
	int umami;
	int pos;
	public Sushi(int pos, int umami) {
		this.pos   = pos;
		this.umami = umami;
	}
}

class Node extends Sushi{
	@Deprecated
	int id;
	@Deprecated
	int dishes;
	int nextPos;
	int totalUmami;

	public Node(int id, int pos, int dishes, int totalUmami) {
		super(pos, -1);
		this.id = id;
		// 次にとることができる寿司は2つ以上離れている
		nextPos = pos + 2;
		this.dishes = dishes;
		this.totalUmami = totalUmami;
	}

	@Override
	public String toString() {
		return "{id=" + id + " dishes=" + dishes + " pos=" + pos + " nextpos=" + nextPos + " totalUmami=" + totalUmami + "}";
	}
}
0