白駿スキー場(22358)

20749 ワード
テキストリンク
スキー場
1.ヒント
1)与えられた図形はDAGである.DPを適用できます.
2)逆方向幹線を単独で保存することにより、簡単に実施することができる.
2.近接
1) DAG
幹線接続aiただし、リフトはbi3.実施
dp関数では、maxはTTTに達しない場合を排除するために十分な小さな値で初期化されなければならない.また、TTT番号の頂点に到達するがk=0 k=0 k=0ではない場合は到達した頂点に戻ればよいので、basecaseはi=T、k=0 i=T、k=0 i=T、k=0 i=T、k=0と定義される.
Javaを追加する時間がないため、Javaを使用してこの問題を解決できません.大会では、このコードをc++に翻訳して提出します.
public class Main {
	static int T;
	static long[][] cache;
	static ArrayList<ArrayList<Pair>> adj;
	static ArrayList<ArrayList<Pair>> adj2; // 역방향 간선
	
	// i번째 지점에서 k번 리프트를 탈 수 있을 때 T까지 가는 최장경로
	static long dp(int i, int k) {
		if (i == T && k == 0) return 0;
		if (cache[i][k] != -1) return cache[i][k];
		long max = Long.MIN_VALUE;
		if (k > 0)
			for (Pair edge : adj2.get(i)) 
				max = Math.max(max, dp(edge.num, k - 1));
		for (Pair edge : adj.get(i)) {
			int there = edge.num; int cost = edge.cost;
			max = Math.max(max, cost + dp(there, k));
		}
		return cache[i][k] = max;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		adj = new ArrayList<>(N + 1); adj2 = new ArrayList<>(N + 1);
		for (int i = 0; i <= N; i++) {
			adj.add(new ArrayList<>());
			adj2.add(new ArrayList<>());
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());
			adj.get(a).add(new Pair(b, t));
			adj2.get(b).add(new Pair(a, 0));
		}
		cache = new long[N + 1][K + 1];
		for (int i = 0; i < N + 1; i++) Arrays.fill(cache[i], -1);
		long ret = dp(S, K);
		if (ret < 0) ret = -1;
		System.out.println(ret);
	}

}
class Pair {
	int num, cost;
	Pair (int n, int c) { num = n; cost = c; }
}
基礎学習総括(八)--Intentで意図と暗黙的意図を表示する使い方
効率的なBitmapのロード(Displaying Bitmaps Efficiently)