根据牛友的思路,修改了一些小bug,以下是代码:
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 节点数k int k = Integer.parseInt(sc.nextLine()); String[] str = sc.nextLine().split(" "); // k个节点转发能力数组 int[][] cap = new int[k + 1][2]; int i = 1; for (String s : str) { String[] str1 = s.split(","); // 转发流量容量 cap[i][0] = Integer.parseInt(str1[0]); // 缓存流量容量 cap[i][1] = Integer.parseInt(str1[1]); i++; } // 初始流量 int n = sc.nextInt(); // DP状态:dp[i][0]为从i发送的数据包,dp[i][1]为第二次从i发送过来的数据包数量 int[][] dp = new int[k + 1][2]; // base case dp[0][0] = n; dp[0][1] = 0; dp[1] = dpFunc(dp[0], cap[1]); int res = Math.min(dp[0][0] + dp[0][1], dp[1][0] + dp[1][1]); if (k == 0) { System.out.println(n); } else if (k == 1) { System.out.println(res); } else { for (int j = 2; j <= k; j++) { // 上一个没坏,从上一个节点(j - 1)直接传到当前节点(j),没有故障 int[] res1 = dpFunc(dp[j - 1], cap[j]); // 上上一个节点(j - 2)传过来,上一个节点(j - 1)出现故障 int[] res2 = dpFunc(dp[j - 2], cap[j]); // 状态转移,选择值最小的一种传递方案 dp[j] = res1[0] + res1[1] <= res2[0] + res2[1] ? res1 : res2; } // 最后一个节点坏掉或者正常情况比较较小值 res = Math.min(dp[k][0] + dp[k][1], dp[k - 1][0] + dp[k - 1][1]); System.out.println(res); } } private static int[] dpFunc(int[] pre, int[] cap) { //pre[0] 上一个节点发送至现节点的数据包 //pre[1] 上一个节点缓存数据包的数量 //cap[0] 当前节点的发送能力 //cap[1] 当前节点的缓存能力 // 第一次发送的数据包数量,根据节点发送能力判断 int first_send = Math.min(pre[0], cap[0]); // 第二次发送的数据包数量,比较三者得到最小值结果: // ①当前节点发送能力cap[0], // 如果大于这个,多余的包也丢弃,无用 // ②当前节点缓存能力和上一个节点缓存数据包数量,cap[1] + pre[1], // 如果这个最小,说明当前节点缓存容量拉满,并且加上前一个节点的缓存包也没达到当前节点发送容量 // ③前一个节点发送过来的包总量经当前节点发送后剩余的数据包数量,包括前一个包发送完剩余包数量,前一个节点缓存数量(把初始状态看作第0个节点) // 这种情况相比于情况②,说明当前节点的缓存能力没达到极限,所以得通过pre[0] - cap[0] + pre[1]算出来 // 但是这里会出现pre[0] - cap[0]是负数的情况(上一个节点发送至现节点的数据包小于当前节点的发送能力),我们不能按照负数算,而是按照0算。 // 所以需要特殊判断一下。 int second_send = 0; if(pre[0] - cap[0] < 0){ second_send = Math.min(pre[1], cap[0]); } else{ second_send = Math.min(pre[0] - cap[0] + pre[1], cap[0]); } second_send = Math.min(second_send, cap[1] + pre[1]); return new int[]{first_send, second_send}; } }
全部评论
(1) 回帖