第一题租服务器,按照租金贪心即可
第二题,赏金猎人,时间区间排序后dp,注意ans用long保存
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Task[] tasks = new Task[n]; for(int i = 0; i < n; i++) { long s = sc.nextLong(); long e = sc.nextLong(); long v = sc.nextLong(); tasks[i] = new Task(s,e,v); } Arrays.sort(tasks); long[] dp = new long[n]; dp[0] = tasks[0].value; for(int i = 0; i < n; i++) { Task t = tasks[i]; int max = t.value; for(int j = 0; j < i; j++) { if(tasks[j].end <= t.start) { max = Math.max(dp[j]+t.value,max); } } dp[i] = max; } long max = 0; //System.out.println(Arrays.toString(dp)); for(int i = 0; i < n; i++) { max = Math.max(dp[i],max); } System.out.println(max); } } class Task implements Comparable<Task> { long start; long end; long value; public Task(int s,int e,long v){ start = s; end = e; value = v; } public int compareTo(Task t) { if(start == t.start) return (int)(end - t.end); else return (int)(start - t.start); } }
全部评论
(6) 回帖