java--study||O.o--动态规划

参考代码:

import java.util.Scanner;

public class Main
{	public static void main(String[] args)
	{	Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int[] boom = new int[n + 1];
		for(int i = 1; i <= n; i++)
			boom[i] = scanner.nextInt();
		boolean[][] map = new boolean[n + 1][n + 1];//邻接矩阵存储
		while(true)
		{	int t1 = scanner.nextInt();
			int t2 = scanner.nextInt();
			if(t1 == 0 && t2 == 0)
				break;
			map[t1][t2] = true;
		}
		scanner.close();
		
		int[] dp = new int[n + 1];//dp[i]为从第i个洞开始挖，可以挖到最多的地雷数
		dp[n] = boom[n];
		int[] index = new int[n + 1];
		for(int i = n - 1; i > 0; i--)
		{	for(int j = i + 1; j <= n; j++)
			{	if(dp[j] > dp[i] && map[i][j])
				{	dp[i] = dp[j];
					index[i] = j;
				}
			}
			dp[i] += boom[i];
		}
		int res = 0;
		int start = 0;
		for(int i = 1; i <= n; i++)
		{	if(dp[i] > res)
			{	res = dp[i];
				start = i;
			}
		}
		while(index[start] > 0)
		{	System.out.print(start + "-");
			start = index[start];
		}
		System.out.println(start);
		System.out.print(res);
	}
}